Casselgren's random-list colouring conjecture for graphs of unbounded degree
Casselgren's random-list colouring conjecture for graphs of unbounded degree
Given positive integers , a random -list-assignment assigns independently to each vertex a uniformly random -element subset of . An -vertex graph is -colourable when it has a proper colouring choosing the colour of every vertex from its assigned list. Let be fixed, and let be an -vertex graph with maximum degree . Casselgren's conjecture. If and , then is asymptotically almost surely -colourable. This extends the known threshold for bounded-degree graphs to graphs whose maximum degree may grow with ; the case 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.