A list analogue of equitable coloring
Alexandr V. Kostochka, Michael J. Pelsmajer, Douglas B. West · Journal of Graph Theory · 2003
Abstract Given lists of available colors assigned to the vertices of a graph G , a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k , then a list coloring is equitable if each color appears on at most $\lceil n (G)/k \rceil$ vertices. A graph is equitably k‐choosable if such a coloring exists whenever the lists all have size k . We prove that G is equitably k ‐choosable when $k \ge {\rm max} \{ {\Delta (G),n(G)/2}\}$ unless G contains $K_{k+1}$ or k is odd and $G=K_{k,k}$ . For forests, the threshold improves to $k \ge 1+\Delta (G)/2$ . If G is a 2‐degenerate graph (given k ≥ 5) or a connected interval graph (other than $K_{k+1}$ ), then G is equitably k ‐choosable when $k\ge \Delta(G)$ . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 166–177, 2003