Győri's asymptotic clique-packing conjecture

About 1 year old · traced to

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 tr−1(n)t_{r-1}(n) denote the number of edges in the Turán graph with r−1r-1 parts. If k∈Rk\in\mathbb{R} satisfies

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

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

νr(G)≥(2−o(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.

References

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.