Balogh, Kostochka and Treglown's conjecture on degree sequences forcing perfect clique tilings

Let n,rNn,r\in\mathbb{N} with rr dividing nn. Suppose that GG is a graph on nn vertices with degree sequence d1dnd_1\leq\ldots\leq d_n satisfying the following conditions:

di(r2)n/r+ifor all i<n/r;d_i\geq (r-2)n/r+i\quad\text{for all }i<n/r; dn/r+1(r1)n/r.d_{n/r+1}\geq (r-1)n/r.

Balogh, Kostochka and Treglown's conjecture. Then GG contains a perfect KrK_r-tiling, that is, a collection of vertex-disjoint copies of KrK_r covering all vertices of GG.

This conjecture seeks a degree-sequence condition forcing a perfect HH-tiling that is best possible in a weaker sense than a Chvátal-type condition. It concerns the degree-sequence analogue of perfect clique-tiling results and remains open in the supplied source context.

Sources & referencesView supporting material

Primary source

Joseph Hyde and Andrew Treglown, “A degree sequence version of the Kühn-Osthus tiling theorem”, arXiv:1909.12670 (2019).

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.