Equitable list colouring

From Egres Open
Jump to: navigation, search

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 [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].


  1. 1.0 1.1 A.V. Kostochka, M.J. Pelsmajer, D.B. West, A List Analogue of Equitable Coloring, DOI link, author link
  2. 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)
  3. J. Zhu, Y. Bu, Equitable and equitable list colorings of graphs, DOI link
  4. X. Zhang, J.-L. Wu, On equitable and equitable list colorings of series–parallel graphs, DOI link
  5. H.A. Kierstead, A.V. Kostochka, Equitable List Coloring of Graphs with Bounded Degree, DOI link, author link
  6. H.A. Kierstead, A.V. Kostochka, M. Mydlarz, E. Szemerédi, A fast algorithm for equitable coloring, DOI link, author link