The degree-sequence conjecture for perfect graph packings

Let γ>0\gamma>0 and let HH be a graph with chromatic number χ(H)=r\chi(H)=r. A perfect HH-packing is a collection of vertex-disjoint copies of HH covering all vertices. Let GG be a graph of order nn with degree sequence d1dnd_1\leq\dots\leq d_n.

Perfect-packing conjecture. There is an integer n0=n0(γ,H)n_0=n_0(\gamma,H) such that, whenever nn0n\geq n_0, H|H| divides nn, and

di(r2)n/r+i+γnfor all i<n/r,d_i\geq (r-2)n/r+i+\gamma n\quad\text{for all }i<n/r,

GG contains a perfect HH-packing.

This is proposed as a likely consequence or application of the preceding perfect KrK_r-packing conjecture. No proof or resolution is given in the source, so the asymptotic generalization remains open.

Sources & referencesView supporting material

Primary source

József Balogh, Alexandr V. Kostochka and Andrew Treglown, “On perfect packings in dense graphs”, arXiv:1110.3490 (2013).

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.