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

Given positive integers kmk \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 k2k \geq 2 be fixed, and let GG be an nn-vertex graph with maximum degree Δ:=Δ(n)\Delta:= \Delta(n). Casselgren's conjecture. If mn1/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.

Sources & referencesView supporting material

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.