Győri's asymptotic clique-packing conjecture

Let GG be an nn-vertex graph. For r fixedr\text{ fixed}, write ur(G) u_r(G) for the maximum number of edge-disjoint rr-cliques in GG, and let tr1(n)t_{r-1}(n) denote the number of edges in the Turán graph with r1r-1 parts. If kRk\in\mathbb{R} satisfies

e(G)=tr1(n)+k,e(G)=t_{r-1}(n)+k,

Győri's conjecture. For every fixed r3r\geq 3,

νr(G)(2o(1))kr.\nu_r(G)\geq \frac{(2-o(1))k}{r}.

This conjecture asymptotically strengthens the Győri–Tuza bound on decomposing the edges of a graph into 22-cliques and rr-cliques, and extends the expected statement to r=3r=3.

Sources & referencesView supporting material

Primary source

József Balogh and Michael C. Wigal, “Packing edge disjoint cliques in graphs”, arXiv:2502.16683 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.