# A List Analogue of Equitable Coloring

A. V. Kostochka, M. J. Pelsmajer, D. B. West

Research output: Contribution to journalReview articlepeer-review

## 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) 166-177 12 Journal of Graph Theory 44 3 https://doi.org/10.1002/jgt.10137 Published - Nov 2003

## Keywords

• Equitable coloring
• Graph coloring
• List coloring
• Outerplanar graph
• Tree

## ASJC Scopus subject areas

• Discrete Mathematics and Combinatorics
• Geometry and Topology

## Fingerprint

Dive into the research topics of 'A List Analogue of Equitable Coloring'. Together they form a unique fingerprint.