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 ⌈n(G)/k⌉ 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 ≥ max{δ(G),n(G)/2} unless G contains Kk+1 or k is odd and G = Kk,k. For forests, the threshold improves to k ≥ 1 + δ(G)/2. If G is a 2-degenerate graph (given k ≥ 5) or a connected interval graph (other than Kk+1), then G is equitably k-choosable When k ≥ δ(G).
Original language | English (US) |
---|---|
Pages (from-to) | 166-177 |
Number of pages | 12 |
Journal | Journal of Graph Theory |
Volume | 44 |
Issue number | 3 |
DOIs | |
State | Published - Nov 2003 |
Keywords
- Equitable coloring
- Graph coloring
- List coloring
- Outerplanar graph
- Tree
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Geometry and Topology