b-coloring of tight graphs

A coloring c of a graph G = (V, E) is a b-coloring if in every color class there is a vertex whose neighborhood intersects every other color class. The b-chromatic number of G, denoted chi(b)(G), is the greatest integer k such that G admits a b-coloring with k colors. A graph G is tight if it has exactly m(G) vertices of degree m(G) - 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 tight graph G is NP-hard even for a connected bipartite graph Kratochvil et al. (2002) [18]. In this paper we show that it is also NP-hard for a tight chordal graph. We also show that the b-chromatic number of a split graph can be computed in polynomial time. We then define the b-closure and the partial b-closure of a tight graph, and use these concepts to give a characterization of tight graphs whose b-chromatic number is equal to m(G). This characterization is used to propose polynomial-time algorithms for deciding whether chi(b)(G) = m(G) for tight graphs that are complement of bipartite graphs, P-4-sparse and block graphs. We also generalize the concept of pivoted tree introduced by Irving and Manlove (1999)[13] and show its relation with the b-chromatic number of tight graphs. (C) 2011 Elsevier B.A. All rights reserved.