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 language | English (US) |
---|---|
Pages (from-to) | 542-553 |
Number of pages | 12 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 18 |
Issue number | 3 |
DOIs | |
State | Published - 2004 |
Keywords
- Brooks' Theorem
- Coloring extension
- List coloring
ASJC Scopus subject areas
- Mathematics(all)