## 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 K_{k+1} or k is odd and G = K_{k,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 K_{k+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