Premium
Degree‐bounded coloring of graphs: Variations on a theme by brooks
Author(s) -
Hakimi S. L.,
Mitchem J.,
Schmeichel E. F.
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200207
Subject(s) - combinatorics , mathematics , bounded function , vertex (graph theory) , complete coloring , graph , fractional coloring , brooks' theorem , degree (music) , colored , upper and lower bounds , discrete mathematics , 1 planar graph , chordal graph , graph power , line graph , physics , mathematical analysis , materials science , composite material , acoustics
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.