2023/03/13 by Carl Johan Casselgren, Casselgren, Carl Johan
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2303.06917
openalex publication_date 2023/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 is a connected graph with maximum degree Δ(G) ≥ 4 that is not a complete graph and P ⊆ V(G) is a set of vertices where either (i) at most Δ(G)-2 colors are forbidden for every vertex in P, and any two vertices of P are at distance at least 4, or (ii) at most Δ(G)-3 colors are forbidden for every vertex in P, and any two vertices of P are at distance at least 3, then there is a proper Δ(G)-coloring of 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.