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
