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) 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 ?(G) ? ( G ) colors. We say that G is b-continuous iff for each k , ?(G)?k?b(G) ? ( 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 Sb(G) 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 I, there exists a graph whose b-spectrum is I and we investigate the complexity of the problem of deciding whether a graph G  is b-continuous, even if b-colorings using ?(G) ? ( G ) and b(G) b ( G ) colors are given.
graph coloring b-chromatic number complexity