Partition the edges of a chordal graph into cliques: is $n^2/6+O(n)$ always enough? (Erdős #81)
Statement
A graph $G$ is chordal if it has no induced cycle of length greater than $3$ (equivalently, every cycle on $\geq 4$ vertices has a chord). Let $G$ be a chordal graph on $n$ vertices. Can the edge set of $G$ always be partitioned into $n^2/6+O(n)$ cliques (complete subgraphs)? That is, is there an absolute constant $C$ such that for every $n$-vertex chordal graph the edges can be split into pairwise edge-disjoint cliques using at most $n^2/6+Cn$ of them?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, else a full written proof with all steps) that the edges of every $n$-vertex chordal graph partition into $n^2/6+O(n)$ cliques — giving an explicit constant in the $O(n)$ term and the covering procedure — OR a disproof exhibiting an explicit family of chordal graphs together with a proof that no clique edge-partition of size $(1/6+\epsilon)n^2$ exists for infinitely many $n$. ADVANCES: improve the general upper bound strictly below the best stated in the background (currently $(1/4-\epsilon)n^2$), i.e. a proof or reproducible certificate that every $n$-vertex chordal graph's edges partition into $\le cn^2+O(n)$ cliques with a constant $c<1/4$; OR improve the split-graph bound below $\frac{3}{16}n^2+O(n)$; OR compute, with a reproducible program and an exhaustiveness certificate, the exact minimum clique edge-partition number of all chordal graphs up to a new record vertex count, sharpening the leading constant. Deliver the proof file, or the improved construction/analysis with proof, or the search code plus certified value table.
Background
Posed by Erdős, Ordman, and Zalcstein [EOZ93], who proved that the edges of any $n$-vertex chordal graph can be partitioned into at most $(1/4-\epsilon)n^2$ cliques for some very small fixed $\epsilon>0$. That the conjectured $n^2/6+O(n)$ is sometimes necessary is shown by an explicit chordal (indeed split) graph: take a clique on $n/3$ vertices, an independent set on $2n/3$ vertices, and all edges between them. A split graph is one whose vertices partition into a clique and an independent set; every split graph is chordal, and Chen, Erdős, and Ordman [CEO94] proved that any split graph's edges can be partitioned into $\frac{3}{16}n^2+O(n)$ cliques — note $\frac{3}{16}=0.1875$ sits between the conjectured $\frac16\approx0.1667$ and the general upper bound $\frac14=0.25$, so even the split-graph case is not yet at the conjectured value. Listed as open on erdosproblems.com/81 (fetched 2026-07-13, status 'open', tagged 'graph theory'); related to erdosproblems.com/1017. No Erdős prize is attached. The attacker's tool: computer search for extremal chordal graphs and better clique-cover constructions/algorithms, exact computation of the minimum clique edge-partition number for chordal graphs up to a new vertex count to pin the constant, and improved analytic upper bounds beating $1/4$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #81 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.