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

✍ Scribed by S. L. Hakimi; J. Mitchem; E. F. Schmeichel

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 876 KB
• Volume: 20
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190200207

✦ Synopsis

Abstract

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.