# Equitable list colouring

Is it true that every graph *G* is equitably *k*-list-colourable for any [math]k \geq \Delta(G)+1[/math]?

## Remarks

This is a conjecture of Kostochka, Pelsmajer, and West ^{[1]}. If true, it would generalize the Hajnal-Szemerédi theorem ^{[2]} 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:

**Conjecture** ^{[1]}. *[math]G[/math] is equitably [math]\Delta(G)[/math]-list-colourable unless it is a complete graph or a complete bipartite graph [math]K_{2m+1,2m+1}[/math].*

The conjecture is known to be true for outerplanar graphs ^{[3]}, series-parallel graphs ^{[4]}, and graphs of maximum degree at most 7 ^{[5]}.
The latter paper gives an algorithm, based on a new algorithm for the Hajnal-Szemerédi theorem ^{[6]}.

## References

- ↑
^{1.0}^{1.1}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