Equitable list‐coloring for graphs of maximum degree 3
Michael J. Pelsmajer · Journal of Graph Theory · 2004
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 ⌈|V(G)|/k⌉ vertices. A graph is equitably k‐choosable if such a coloring exists whenever the lists all have size k. Kostochka, Pelsmajer, and West introduced this notion and conjectured that G is equitably k‐choosable for k > Δ (G). We prove this for Δ(G) = 3. We also show that every graph G is equitably k‐choosable for k ≥ Δ(G)(Δ(G)−1)/2 + 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 1–8, 2004