Gustavsson–Nash-Williams conjecture on clique decompositions

Let r3r\ge 3. A graph GG is KrK_r-divisible when its number of edges is divisible by (r2)\binom{r}{2} and every vertex degree is divisible by r1r-1.

Gustavsson–Nash-Williams conjecture. For every r3r\ge 3, there exists an n0=n0(r)n_0=n_0(r) such that every KrK_r-divisible graph GG on nn0n\ge n_0 vertices with

δ(G)(11/(r+1))n\delta(G)\ge (1-1/(r+1))n

\nhas a KrK_r-decomposition.

This conjecture predicts the asymptotically sharp minimum-degree threshold for decomposing divisible graphs into copies of a clique. It is attributed to Nash-Williams for triangles and to Gustavsson in general; the supplied source gives no resolution status.

Sources & referencesView supporting material

Primary source

Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery and Deryk Osthus, “On the decomposition threshold of a given graph”, arXiv:1603.04724 (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.