## 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)