Erdős Problem #81
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A chordal graph is one that has no induced cycle of length four or more. Erdős #81 asks whether the edges of every chordal graph on \(n\) vertices can be partitioned, without overlap, into at most
complete subgraphs (cliques). Every edge must belong to exactly one selected clique. A clique covering that permits the same edge to appear more than once is not an answer.
A small example
In a star \(K_{1,4}\), no triangle exists. Each edge must therefore be its own two-vertex clique, and exactly four cliques are needed. In a complete graph \(K_n\), the entire edge set forms one clique. Thus chordality alone does not make the clique-partition number a fixed function of the number of edges; it depends on how triangles overlap.
For the sharp asymptotic example, join every vertex of a clique on about \(n/3\) vertices to an independent set of about \(2n/3\) vertices. This split graph is chordal. Its dense pattern of shared clique edges makes edge-disjoint clique partitioning unexpectedly expensive, producing the conjectured \(n^2/6+O(n)\) scale.
What is known
The exact coefficient \(1/6\) remains OPEN. The primary 1993 paper by Erdős, Ordman and Zalcstein, Clique partitions of chordal graphs, Combinatorics, Probability and Computing 2 (1993), 409–415, explicitly states both the extremal example and a universal upper bound of \((1-c)n^2/4\) for some absolute \(c>0\). This improves the elementary bound of about \(n^2/4\), but does not reach \(n^2/6\).
Chen, Erdős and Ordman later obtained \((3/16)n^2+O(n)\) for split graphs, still above \(n^2/6\). Split graphs form a proper subclass of chordal graphs, so an argument valid only for split graphs does not automatically cover every chordal graph.
GCL's current state
The original protected assignment is #1350. The 1993 publisher primary abstract was checked. Its universal constant \(c\) is not independently reconstructed from the full paper, and recent community-proposed refinements have not been independently adjudicated. Both pinned and maintained statuses are OPEN.
An authenticated RESULT/1 source report is posted on the original issue. It is unadjudicated source evidence, not independent proof certification or editorial admission.
What remains
A bounded successor is to implement an exact edge-partition integer program for chordal graphs with at most seven vertices. Each variable represents a clique of size at least two; impose equality one over the cliques containing every edge and minimize the number selected. Enumerate chordal graph isomorphism classes and compare split-graph examples. Acceptance: a partition certificate with each edge appearing exactly once; falsification: a nonchordal test graph entering the sample, an uncovered edge, or a repeated edge. These finite fixtures test semantics, not the asymptotic conjecture.
Sources and claim boundaries
- Erdős, Ordman and Zalcstein, Clique partitions of chordal graphs, 1993, publisher primary abstract, pp. 409–415.
- Maintained Erdős #81, original sharp split-graph construction and bounds.
- GCL original issue #1350.
No theorem improving the 1993 universal bound, full proof replay, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1350 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.