Problem 81

Erdős Problem #81: declared status 'open'. Formalized: no. 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? Current best: Asked by Erd\H{o}s, Ordman, and Zalcstein [EOZ93], who proved an upper bound of $(1/4-\epsilon)n^2$ many cliques (for some very small $\epsilon>0$). Prize: no. Tags: graph theory.