Alon's logarithmic bound conjecture for bipartite graph list coloring

From papers

Let GG be a bipartite graph, and let Δ(G)\Delta(G) denote its maximum degree. Alon's conjecture. There exists a constant cc such that

χ(G)clogΔ(G).\chi_\ell(G) \leq c \log \Delta(G).

This conjecture concerns whether bipartite graphs have list chromatic number only logarithmic in maximum degree; the supplied text presents it as an open problem.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Nandana K Vasudevan, K Somasundaram and N Narayanan, “List-Coloring and Chromatic-Choosability – A Dynamic Survey”, arXiv:2606.31702 (2026).

Solutions 0

No solutions have been posted yet.