List chromatic number conjecture for multipartite uniform hypergraphs

About 4 years old · traced to

Let k⩾2k\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.

References

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.

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.