On the b-continuity property of graphs

This paper deals with b-colorings of a graph G, that is, proper colorings in which for each color c, there exists at least one vertex colored by c such that its neighbors are colored by each other color. The b-chromatic number b(G) of a graph G is the maximum number of colors for which G has a b-coloring. It is easy to see that every graph G has a b-coloring using X(G) colors. We say that G is b-continuous iff for each k, X(G) <= k <= b(G), there exists a b-coloring with k colors. It is well known that not all graphs are b-continuous. We call b-spectrum S-b(G) of G to be the set of integers k for which there is a b-coloring of G by k colors. We show that for any finite integer set 1, there exists a graph whose b-spectrurn is I and we investigate the complexity of the problem of deciding whether a graph G is b-continuous, even if b-colorings using Z(G) and b(G) colors are given. (C) 2007 Elsevier B.V. All rights reserved.