Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a chordal graph on vertices - that is, has no induced cycles of length greater than . Can the edges of be partitioned into many cliques?
Source: erdosproblems.com/81
A full solution has been claimed but not yet accepted. The statement is true.
The site labels the problem OPEN (page last edited 28
December 2025; proof-claims tab and thread as of 2026-10-07), and the
frontmatter standing is derived from the five claim pages under claims/:
three pending full claims assert the answer yes, so the standing is claimed,
and none is refereed, independently reviewed or adopted by the site. In order
of posting: Agbanwa's Zenodo note, for the chordal graphs with a
maximum clique whose edge deletion lowers the clique number by at most one, a
class that excludes the extremal split graphs
(claim page (Agbanwa, 2026),
partial, posted on the thread and not registered on the tab); Traverso's Paper
III, for split graphs with a Lean freeze
(claim page (Traverso, 2026),
partial); the manuscript registered by Morluto, Luo, Huang and Lee, whose
author line reads "Anonymous", generated with GPT-5.6 and GPT-6 Astra,
giving the eventual maximum and hence
for all chordal graphs, with a Lean proof conditional on three
literature theorems
(claim page (Morluto Luo Huang Lee, 2026),
full); Okechukwu's arXiv preprint on graphs of bounded simplicial defect,
whose chordal case gives , announced on the thread with a
priority dispute
(claim page (Okechukwu, 2026),
full); and Traverso's Paper IV, at every order
with pieces of order at most four and a Lean proof the author reports as
unconditional
(claim page (Traverso, 2026),
full). Two results get no claim page because they settle no instance of the
question. The proof-claims tab's entry of 10 August 2026 by Cipollini (claim
201), an Overleaf manuscript partitioning the edges of every chordal graph
into cliques, written by him with LaTeX assistance and minor
polishing by GPT-5.6 Sol as the tab says, gives the sharp quadratic
coefficient and names the gap between and as the remaining
difficulty; it proves the error for no class of chordal graphs, and
the later full claims credit it as an independent first-order bound. The
thread's comment of 19 June 2026, not registered on the tab, reports an
explicit form with of the bound of Erdős, Ordman
and Zalcstein, obtained with ChatGPT 5.5 Pro and formalized by Aristotle, as
the comment says, which sharpens a known weaker bound. The site states that
a listing on the proof-claims tab is no guarantee of correctness.