Casselgren's random-list colouring conjecture for graphs of unbounded degree

About 2 years old · traced to

Given positive integers k≤mk \leq m, a random (k,m)(k,m)-list-assignment assigns independently to each vertex a uniformly random kk-element subset of {1,…,m}\{1,\ldots,m\}. An nn-vertex graph is (k,m)(k,m)-colourable when it has a proper colouring choosing the colour of every vertex from its assigned list. Let k≥2k \geq 2 be fixed, and let GG be an nn-vertex graph with maximum degree Δ:=Δ(n)\Delta:= \Delta(n). Casselgren's conjecture. If m≫n1/k2Δ1/km \gg n^{1/k^2}\Delta^{1/k} and m≫Δm \gg \Delta, then GG is asymptotically almost surely (k,m)(k,m)-colourable. This extends the known threshold for bounded-degree graphs to graphs whose maximum degree may grow with nn; the case k=2k=2 is known, as is the bounded-degree case, while the general conjecture remains open.

References

Primary source

Dan Hefetz and Michael Krivelevich, “Colouring graphs from random lists”, arXiv:2402.09998 (2024).

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.