The degree-sequence conjecture for perfect graph packings

About 15 years old · traced to

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 d1≤⋯≤dnd_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 n≥n0n\geq n_0, ∣H∣|H| divides nn, and

di≥(r−2)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.

References

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.