Krivelevich–Alon conjecture on the list chromatic number of bipartite graphs
Krivelevich–Alon conjecture on the list chromatic number of bipartite graphs
Let be a bipartite graph with maximum degree at most , and let be a positive integer. The graph is -choosable if every assignment of lists of colours to its vertices admits a proper colouring from those lists. Krivelevich–Alon conjecture. There is an absolute constant such that is -choosable whenever . This conjecture extends the asymptotic behaviour of complete bipartite graphs to all bipartite graphs of maximum degree . The source presents it as an open conjecture and notes that the paper's results give partial progress, especially in asymmetric cases.
Sources & referencesView supporting material
Primary source
Noga Alon, Stijn Cambie and Ross J. Kang, “Asymmetric list sizes in bipartite graphs”, arXiv:2004.07457 (2021).
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.