Claim in Erdős problems: literature check, graph theory (1)
A published paper or arXiv preprint answers the main question of Erdős Problem #81 (theorem erdos_81 in formal-conjectures) in full (proof, disproof, or the exact value asked for) with no hypotheses beyond the problem's own.
Let G be a chordal graph on n vertices - that is, G has no induced cycles of length greater than 3. Can the edges of G be partitioned into n^2/6+O(n) many cliques?
- [EOZ93] Erdős, Paul and Ordman, Edward T. and Zalcstein, Yechezkel, Clique partitions of chordal graphs. Combin. Probab. Comput. (1993), 409–415.
- [CEO94] Chen, Guan-Tao and Erdős, Paul and Ordman, Edward T., Clique partitions of split graphs. Combinatorics, graph theory, algorithms and applications (Beijing, 1993) (1994), 21–30.
Verdict: candidate reference, not checked by a mathematician
Evidence for
“The same expression is an upper bound up to an additive constant depending only on $s$ at every order. In particular, every chordal graph has clique partition number at most $n^2/6+n/6+O(1)$, answering a question of Erdős, Ordman and Zalcstein.”
Note: O. Okechukwu (2026), Clique partitions and bounded simplicial defect, arXiv:2609.20871 (v1 15 Sep 2026, unrefereed, single author). Match: Cor. 1.2 (s=0 case of Thm 1.1) gives cp(G) <= floor(n(n+1)/6)+K_0 for every chordal G at every order n, cliques of order >= 2 as in IsCliqueEdgePartition; with C = 1/6+K_0 this is exactly erdos_81, answer yes. K_0 is not explicit; proof not yet checked by experts.
Evidence against
None yet.