We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Brooks' theorem with forbidden colors.
- Authors
Casselgren, Carl Johan
- Abstract
We consider extensions of Brooks' classic theorem on vertex coloring where some colors cannot be used on certain vertices. In particular we prove that if G $G$ is a connected graph with maximum degree Δ(G)≥4 ${\rm{\Delta }}(G)\ge 4$ that is not a complete graph and P⊆V(G) $P\subseteq V(G)$ is a set of vertices where either (i)at most Δ(G)−2 ${\rm{\Delta }}(G)-2$ colors are forbidden for every vertex in P $P$, and any two vertices of P $P$ are at distance at least 4, or(ii)at most Δ(G)−3 ${\rm{\Delta }}(G)-3$ colors are forbidden for every vertex in P $P$, and any two vertices of P $P$ are at distance at least 3,then there is a proper Δ(G) ${\rm{\Delta }}(G)$‐coloring of G $G$ respecting these constraints. In fact, we shall prove that these results hold in the more general setting of list colorings. These results are sharp.
- Subjects
COLORS; GRAPH connectivity; COMPLETE graphs; GRAPH coloring
- Publication
Journal of Graph Theory, 2024, Vol 105, Issue 3, p373
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.23039