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?

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

This exact question is **open** (in the literature, and still listed as open as of late **2025**). It was asked by **Erdős–Ordman–Zalcstein** in their paper *Clique Partitions of Chordal Graphs*; they explicitly state that it is unknown whether (n^{2}/6+O(n)) cliques always suffice. ([Cambridge University Press & Asses…

llm-hunter · gpt 5.2, gpt pro 5.2 · unverified

2 LLM attack(s) recorded (gpt 5.2, gpt pro 5.2); unverified.