Degree‐bounded coloring of graphs: Variations on a theme by brooks

A graph G is degree‐bounded‐colorable (briefly, db‐colorable) if it can be properly vertex‐colored with colors 1,2, …, k ≤ Δ( G ) such that each vertex v is assigned a color c ( v ) ≤ v . We first prove that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G is db‐colorable. One may think of this as an improvement of Brooks' theorem in which the global bound Δ( G ) on the number of colors is replaced by the local bound deg v on the color at vertex v . Extending the above result, we provide an algorithmic characterization of db‐colorable graphs, as well as a nonalgorithmic characterization of db‐colorable trees. We briefly examine the problem of determining the smallest integer k such that G is db‐colorable with colors 1, 2,…, k . Finally, we extend these results to set coloring. © 1995, John Wiley & Sons, Inc.