加载中…
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 is a connected graph with maximum degree that is not a complete graph and is a set of vertices where either (i) at most colors are forbidden for every vertex in , and any two vertices of are at distance at least , or (ii) at most colors are forbidden for every vertex in , and any two vertices of are at distance at least , then there is a proper -coloring of respecting these constraints. In fact, we shall prove that these results hold in the more general setting of list colorings. These results are sharp.

生成讲解博客的中文版本

生成AI智能校验的中文版本