2023/09/02 by H. A. Kierstead, Kierstead, H. A., Alexandr Kostochka +3
Computer Science · Mathematics · #05C07 #05C10 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2309.00989
openalex publication_date 2023/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
If L is a list assignment of r colors to each vertex of an n-vertex graph G, then an equitable L-coloring of G is a proper coloring of vertices of G from their lists such that no color is used more than \lceil n/r\rceil times. A graph is equitably r-choosable if it has an equitable L-coloring for every r-list assignment L. In 2003, Kostochka, Pelsmajer and West (KPW) conjectured that an analog of the famous Hajnal-Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer r every graph G with maximum degree at most r-1 is equitably r-choosable. The main result of this paper is that for each r≥ 9 and each planar graph G, a stronger statement holds: if the maximum degree of G is at most r, then G is equitably r-choosable. In fact, we prove the result for a broader class of graphs -- the class B of the graphs in which each bipartite subgraph B with |V(B)|≥3 has at most 2|V(B)|-4 edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in B, in particular, for all planar graphs.