Packing edge disjoint cliques in graphs

2025/02/23 by Balogh, József, Wigal, Michael C.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2502.16683

Abstract

Let r ≥ 3 be fixed and G be an n-vertex graph. A long-standing conjecture of Győri states that if e(G) = t_r-1(n) + k, where t_r-1(n) denotes the number of edges of the Turán graph on n vertices and r - 1 parts, then G has at least (2 - o(1))k/r edge disjoint r-cliques. We prove this conjecture.

Related

• Turán numbers of vertex-disjoint cliques in r-partite graphs
• Joints in graphs
• Packing K_rs in bounded degree graphs
• Turán number of four vertex-disjoint cliques
• Induced Turán numbers