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 languageEnglish (US)
Pages (from-to)166-177
Number of pages12
JournalJournal of Graph Theory
Volume44
Issue number3
DOIs
StatePublished - Nov 2003

Keywords

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

ASJC Scopus subject areas

  • Geometry and Topology

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

Cite this