TY - JOUR
T1 - Equitable List Coloring of Planar Graphs With Given Maximum Degree
AU - Kierstead, H. A.
AU - Kostochka, Alexandr
AU - Xiang, Zimu
N1 - We thank the referees for the helpful comments. Research is supported in part by NSF (Grant DMS\u20102153507), NSF RTG (Grant DMS\u20101937241), and Campus Research Board Award RB24000 of the University of Illinois Urbana\u2010Champaign.
PY - 2025/4
Y1 - 2025/4
N2 - If (Formula presented.) is a list assignment of (Formula presented.) colors to each vertex of an (Formula presented.) -vertex graph (Formula presented.), then an equitable (Formula presented.) -coloring of (Formula presented.) is a proper coloring of vertices of (Formula presented.) from their lists such that no color is used more than (Formula presented.) times. A graph is equitably (Formula presented.) -choosable if it has an equitable (Formula presented.) -coloring for every (Formula presented.) -list assignment (Formula presented.). 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 (Formula presented.) every graph (Formula presented.) with maximum degree at most (Formula presented.) is equitably (Formula presented.) -choosable. The main result of this paper is that for each (Formula presented.) and each planar graph (Formula presented.), a stronger statement holds: if the maximum degree of (Formula presented.) is at most (Formula presented.), then (Formula presented.) is equitably (Formula presented.) -choosable. In fact, we prove the result for a broader class of graphs—the class (Formula presented.) of the graphs in which each bipartite subgraph (Formula presented.) with (Formula presented.) has at most (Formula presented.) edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in (Formula presented.), in particular, for all planar graphs. We also introduce the new stronger notion of strongly equitable (SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE (Formula presented.) -choosable, then it is both equitably (Formula presented.) -choosable and equitably (Formula presented.) -colorable, while neither of being equitably (Formula presented.) -choosable and equitably (Formula presented.) -colorable implies the other.
AB - If (Formula presented.) is a list assignment of (Formula presented.) colors to each vertex of an (Formula presented.) -vertex graph (Formula presented.), then an equitable (Formula presented.) -coloring of (Formula presented.) is a proper coloring of vertices of (Formula presented.) from their lists such that no color is used more than (Formula presented.) times. A graph is equitably (Formula presented.) -choosable if it has an equitable (Formula presented.) -coloring for every (Formula presented.) -list assignment (Formula presented.). 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 (Formula presented.) every graph (Formula presented.) with maximum degree at most (Formula presented.) is equitably (Formula presented.) -choosable. The main result of this paper is that for each (Formula presented.) and each planar graph (Formula presented.), a stronger statement holds: if the maximum degree of (Formula presented.) is at most (Formula presented.), then (Formula presented.) is equitably (Formula presented.) -choosable. In fact, we prove the result for a broader class of graphs—the class (Formula presented.) of the graphs in which each bipartite subgraph (Formula presented.) with (Formula presented.) has at most (Formula presented.) edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in (Formula presented.), in particular, for all planar graphs. We also introduce the new stronger notion of strongly equitable (SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE (Formula presented.) -choosable, then it is both equitably (Formula presented.) -choosable and equitably (Formula presented.) -colorable, while neither of being equitably (Formula presented.) -choosable and equitably (Formula presented.) -colorable implies the other.
KW - equitable coloring
KW - equitable list coloring
KW - planar graphs
KW - strongly equitable list coloring
UR - http://www.scopus.com/inward/record.url?scp=85212044467&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85212044467&partnerID=8YFLogxK
U2 - 10.1002/jgt.23203
DO - 10.1002/jgt.23203
M3 - Article
AN - SCOPUS:85212044467
SN - 0364-9024
VL - 108
SP - 832
EP - 838
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 4
ER -