On the $4$-clique cover number of graphs

Abstract

In 1966, Erdős, Goodman, and Pósa proved that $\lfloor n^2/4\rfloor$ cliques are sufficient to cover all edges in any $n$-vertex graph, with tightness achieved by the balanced complete bipartite graph. This result was generalized by Dau, Milenkovic, and Puleo, who showed that at most $\lfloor \frac{n}{3}\rfloor \lfloor \frac{n+1}{3}\rfloor \lfloor \frac{n+2}{3}\rfloor$ cliques are needed to cover all triangles in any $n$-vertex graph $G$, and the bound is best possible as witnessed by the balanced complete tripartite graph. They further conjectured that for $t\ge 4$, the $t$-clique cover number is maximized by the Turán graph $T_{n,t}$. We confirm their conjecture for $t=4$ using novel techniques, including inductive frameworks, greedy partition method, local adjustments, and clique-counting lemmas by Erdős and by Moon and Moser.

18 pages