A list analogue of equitable coloring

✍ Scribed by A. V. Kostochka; M. J. Pelsmajer; D. B. West

• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 125 KB
• Volume: 44
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10137

✦ Synopsis

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