Article in press
Authors:
Title:
Equitable choosability of prism graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-05-22 , Revised: 2023-11-13 , Accepted: 2023-11-13 , Available online: 2024-01-15 , https://doi.org/10.7151/dmgt.2534
Abstract:
A graph $G$ is equitably $k$-choosable if, for every $k$-uniform list assignment
$L$, $G$ is $L$-colorable and each color appears on at most
$\left\lceil |V(G)|/k\right\rceil$ vertices. Equitable list-coloring was
introduced by Kostochka, Pelsmajer, and West in 2003 [A list analogue of
equitable coloring, J. Graph Theory 44 (2003) 166–177]. They
conjectured that a connected graph $G$ with $\Delta(G)\geq 3$ is equitably
$\Delta(G)$-choosable, as long as $G$ is not complete or $K_{d,d}$ for odd $d$.
In this paper, we use a discharging argument to prove their conjecture for the
infinite family of prism graphs.
Keywords:
list coloring, equitable list coloring, prism graph, reducible configuration, discharging
References:
- B.L. Chen, K.-W. Lih and P.-L. Wu, Equitable coloring and the maximum degree, European J. Combin. 15 (1994) 443–447.
https://doi.org/10.1006/eujc.1994.1047 - R. Diestel, Graph Theory, Grad. Texts in Math. 173 (Springer, Berlin, Heidelberg, 2017).
https://doi.org/10.1007/978-3-662-53622-3 - A. Dong and X. Zhang, Equitable coloring and equitable choosability of graphs with small maximum average degree, Discuss. Math. Graph Theory 38 (2018) 829–839.
https://doi.org/10.7151/dmgt.2049 - P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Util. Math., (Winnipeg, Man. 1980) 125–157.
- A.V. Kostochka, M.J. Pelsmajer and D.B. West, A list analogue of equitable coloring, J. Graph Theory 44 (2003) 166–177.
https://doi.org/10.1002/jgt.10137 - M.J. Pelsmajer, Equitable list-coloring for graphs of maximum degree $3$, J. Graph Theory 47 (2004) 1–8.
https://doi.org/10.1002/jgt.20011 - V.G. Vizing, Coloring the graph vertices with some prescribed colors, Methods of Discrete Analysis in the Theory of Codes and Schemes 29 (1976) 3–10.
- W.-F. Wang and K.-W. Lih, Equitable list coloring of graphs, Taiwanese J. Math. 8 (2004) 747–759.
https://doi.org/10.11650/twjm/1500407716 - J. Zhu and Y. Bu, Equitable and equitable list colorings of graphs, Theoret. Comput. Sci. 411 (2010) 3873–3876.
https://doi.org/10.1016/j.tcs.2010.06.027
Close