bb-coloring of tight graphs

A coloring cc of a graph G=(V,E)G=(V,E) is a bb-coloring   if in every color class there is a vertex whose neighborhood intersects every other color class. The bb-chromatic number   of GG, denoted χb(G)χb(G), is the greatest integer kk such that GG admits a bb-coloring with kk colors. A graph GG is tight   if it has exactly m(G)m(G) vertices of degree m(G)−1m(G)−1, where m(G)m(G) is the largest integer mm such that GG has at least mm vertices of degree at least m−1m−1. Determining the bb-chromatic number of a tight graph GG 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 bb-chromatic number of a split graph can be computed in polynomial time. We then define the bb-closure and the partial bb-closure of a tight graph, and use these concepts to give a characterization of tight graphs whose bb-chromatic number is equal to m(G)m(G). This characterization is used to propose polynomial-time algorithms for deciding whether χb(G)=m(G)χb(G)=m(G) for tight graphs that are complement of bipartite graphs, P4P4-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 bb-chromatic number of tight graphs.