Casselgren–Häggkvist conjecture on random list coloring of balanced complete-bipartite line graphs
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.
Sources & referencesView supporting material
Primary source
Vikrant Ashvinkumar and Charles Kenney, “Palette Sparsification via FKNP”, arXiv:2408.12835 (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.