---

Claim. Say that a chordal graph $G$ with clique number $\omega$ satisfies the weak clique-drop hypothesis if it has a maximum clique $K$ with $\omega(G-E(K))\ge\omega-1$: deleting the edges inside $K$ lowers the clique number by at most one. Jamal Agbanwa, Partial Results on Clique Edge-Partitions of Chordal Graphs, Zenodo preprint, first version deposited 17 June 2026 (the claim's date) and second version of 20 June 2026 (Zenodo record 20778270, whose title page reads A Conditional $n^2/6+O(n)$ Bound for Clique Edge-Partitions of Chordal Graphs), proves as its Theorem 5.3 that every chordal graph $G$ on $n$ vertices satisfying the hypothesis has

$$\mathrm{cp}(G)\le\frac{(2n-1)^2}{24}+2=\frac{n^2}{6}+O(n),$$

the bound asked in Problem 81 for that class. The proof takes $K$ as one piece of the partition, covers the rest of the graph by one maximum clique and single edges, so that $\mathrm{cp}(G)\le2+|E(G)|-(\omega-1)^2$, bounds $|E(G)|$ by $(\omega-1)n-\binom{\omega}{2}$ through a perfect elimination ordering, and maximizes the resulting concave quadratic in $\omega-1$. The note also computes exactly $\mathrm{cp}(G_m)=n^2/6+n/6$ for the split graphs $G_m$ of Erdős, Ordman and Zalcstein on $n=3m$ vertices, by a linear-programming dual certificate and a one-factorization, shows that $G_m$ fails the hypothesis for $m\ge3$, and shows that every tree with at least two vertices satisfies it. The author posted the note on the site's thread on 20 June 2026 and credits Claude Sonnet 4.6, which the acknowledgements say was used substantially in developing and drafting the note.

Submission note. Posted to the site's forum by Jamal Agbanwa on 20 June 2026:

This is a partial result I have on Erdős Problem #81, developed with assistance from Claude Sonnet 4.6. The note does not claim to solve the full problem. Its main result is a conditional $n^2/6+O(n)$ upper bound for chordal graphs satisfying the weak Clique-Drop Hypothesis (wCDH), together with a self-contained exact computation for the Erdős-Ordman-Zalcstein lower-bound family.

Full document: https://zenodo.org/records/20778270

Covers. The statement of Problem 81 restricted to the chordal graphs satisfying the weak clique-drop hypothesis, with the explicit bound $(2n-1)^2/24+2$. Chordal graphs in which deleting the edges of any maximum clique lowers the clique number by two or more are not covered; the extremal split graphs $G_m$ lie in that class, so, as the note's Remark 8.3 says, the question as posed is not settled by it. The pending full claims of Morluto, Luo, Huang and Lee, Okechukwu and Traverso assert the bound for all chordal graphs.

Depends on. Nothing in this wiki.

Formalization. The file Lean formalisation of theorems in the folder #81 of the author's JAgbanwa/Erdos-Problems repository, at the commit linked above, states that it formalizes the proof that every graph satisfying wCDH has cp G ≤ 2 + (2n-1)^2/24, that the formalization was obtained by Aristotle from Harmonic, and that its Lean version is 4.28.0; the note's Remark 5.4 and its reference [6] credit the formalization to W. van Doorn. Its predicate wCDH requires a perfect elimination ordering and a maximum clique whose edge deletion keeps the clique number at least $\omega-1$, and its main_theorem states $\mathrm{cp}(G)\le2+(2n-1)^2/24$ over the rationals for a graph on a nonempty finite vertex type. The file was first committed on 18 June 2026. This corpus has not built, printed or audited it, so it is no formalized evidence.

Standing. Claimed: a Zenodo preprint with no refereed version and no outside review known to this corpus, not registered on the site's proof-claims tab; the thread post announcing it drew no reply, and the site labels the problem OPEN (page last edited 28 December 2025, as of 2026-10-07).