Casselgren–Häggkvist conjecture on random list coloring of balanced complete-bipartite line graphs
Let be an even natural number and let be the line graph of a complete bipartite graph. Thus has vertices and maximum degree . For each vertex , choose uniformly and independently. Casselgren–Häggkvist conjecture. There is a constant such that, whenever ,
This conjecture was posed after Johansson asked for a threshold for random list coloring. It has since been proved by several papers, so the conjecture is solved.
References
Primary source
Vikrant Ashvinkumar and Charles Kenney, “Palette Sparsification via FKNP”, arXiv:2408.12835 (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.