b-coloring of m-tight graphs

A given k-coloring c of a graph G=(V,E) is a b-coloring if for every color class ci, 1⩽i⩽k, there is a vertex colored i whose neighborhood intersect every other color class cj of c. The b-chromatic number of G is the greatest integer k such that G admits a b-coloring with k colors. A graph G is m-tight if it has exactly m=m(G) vertices of degree exactly m−1, where m(G) is the largest integer m such that G has at least m vertices of degree at least m−1. Determining the b-chromatic number of a m-tight graph G is NP-hard [Jan Kratochvil, Zsolt Tuza, and Margit Voigt. On the b-chromatic number of graphs. In Proc. of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 310–320. Springer-Verlag, 2002]. In this paper, we define the b-closure and the partial b-closure of a m-tight graph. These concepts were used to give a characterization of m-tight graphs whose b-chromatic number is equal to m. To illustrate an application of our characterization, we provide some examples for which we can answer in polynomial time whether χb(G)