Premium
A list analogue of equitable coloring
Author(s) -
Kostochka A. V.,
Pelsmajer M. J.,
West D. B.
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10137
Subject(s) - combinatorics , list coloring , mathematics , vertex (graph theory) , graph , complete coloring , fractional coloring , edge coloring , discrete mathematics , graph power , line graph
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