Precoloring extensions of Brooks' theorem

Michael O. Albertson, Alexandr V. Kostochka, Douglas B. West

Research output: Contribution to journalArticlepeer-review

Abstract

Let G be a connected graph with maximum degree k (other than a complete graph or odd cycle), let W be a precolored set of vertices in G inducing a subgraph F, and let D be the minimum distance in G between components of F. If the components of F are complete graphs and D ≥ 8 (for k ≥ 4) or D ≥ 10 (for k = 3), then every proper k-coloring of F extends to a proper fc-coloring of G. If the components of F are single vertices and D ≥ 8, and the vertices outside W are assigned color lists of size k, then every k-coloring of F extends to a proper coloring of G with the color on each vertex chosen from its list. These results are sharp.

Original languageEnglish (US)
Pages (from-to)542-553
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume18
Issue number3
DOIs
StatePublished - 2004

Keywords

  • Brooks' Theorem
  • Coloring extension
  • List coloring

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Precoloring extensions of Brooks' theorem'. Together they form a unique fingerprint.

Cite this