Equitable list colouring
Is it true that every graph G is equitably k-list-colourable for any [math]k \geq \Delta(G)+1[/math]?
This is a conjecture of Kostochka, Pelsmajer, and West . If true, it would generalize the Hajnal-Szemerédi theorem  which states that every graph G has an equitable k-colouring for any [math]k \geq \Delta(G)+1[/math]. The following strengthening is also open:
The conjecture is known to be true for outerplanar graphs , series-parallel graphs , and graphs of maximum degree at most 7 . The latter paper gives an algorithm, based on a new algorithm for the Hajnal-Szemerédi theorem .
- A.V. Kostochka, M.J. Pelsmajer, D.B. West, A List Analogue of Equitable Coloring, DOI link, author link
- A. Hajnal, E. Szemerédi, Proof of a conjecture of Erdős, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pp. 601-623 (1970)
- J. Zhu, Y. Bu, Equitable and equitable list colorings of graphs, DOI link
- X. Zhang, J.-L. Wu, On equitable and equitable list colorings of series–parallel graphs, DOI link
- H.A. Kierstead, A.V. Kostochka, Equitable List Coloring of Graphs with Bounded Degree, DOI link, author link
- H.A. Kierstead, A.V. Kostochka, M. Mydlarz, E. Szemerédi, A fast algorithm for equitable coloring, DOI link, author link