List chromatic number conjecture for multipartite uniform hypergraphs

From papers

Let k2k\geqslant 2, let Δ\Delta be sufficiently large, and let HH be a kk-partite kk-graph of maximum degree at most Δ\Delta. Write χ(H)\chi_\ell(H) for the list chromatic number of HH. List chromatic number conjecture for kk-partite kk-graphs. There is a constant c=c(k)>0c=c(k)>0 such that

χ(H)clogΔ.\chi_\ell(H)\leqslant c\log\Delta.

This extends the Alon–Krivelevich conjecture from bipartite graphs to kk-partite kk-graphs and is supported by results for random and complete multipartite hypergraphs. The case k=2k=2 matches the cited bipartite conjecture; the general case remains open.

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

Abhishek Dhawan, “List colorings of k-partite k-graphs”, arXiv:2311.03111 (2025).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2211.09048.

Solutions 0

No solutions have been posted yet.