z-logo
open-access-imgOpen Access
Precoloring Extensions of Brooks' Theorem
Author(s) -
Michael O. Albertson,
Alexandr Kostochka,
Douglas B. West
Publication year - 2004
Publication title -
siam journal on discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.843
H-Index - 66
eISSN - 1095-7146
pISSN - 0895-4801
DOI - 10.1137/s0895480103425942
Subject(s) - combinatorics , mathematics , vertex (graph theory) , complete coloring , graph , list coloring , brooks' theorem , fractional coloring , discrete mathematics , graph power , line graph
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\ge 8$ (for $k\ge 4$) or $D\ge 10$ (for k = 3), then every proper k-coloring of F extends to a proper k-coloring of G. If the components of F are single vertices and $D\ge 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom