DEGREE-BOUNDED COLORING OF GRAPHS - VARIATIONS ON A THEME BY BROOKS

A graph G is deg ree-bounded-colorable (briefly, db-colorable) if it c an be properly vertex-colored with colors 1,2,..., k less than or equa l to Delta(G) such that each vertex v is assigned a color c(v) less th an or equal to deg 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 d b-colorable. One may think of this as an Improvement of Brooks' theore m in which the global bound Delta(G) on the number of colors is replac ed by the local bound deg v on the color at vertex v. Extending the ab ove 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 inte ger k such that G is db-colorable with colors 1,2,..., k. Finally, we extend these results to set coloring. (C) 1995 John Wiley & Sons, Inc.