2025/06/12 by Chen, Yihan, Jialin He, He, Jialin +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2506.10478
openalex publication_date 2025/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1966, Erdős, Goodman, and Pósa proved that \lfloor n2/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 ≥ 4, the t-clique cover number is maximized by the Turán graph Tn,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.