On the b-coloring of tight graphs

A coloring c of a graph (G=(V,E)) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least (m-1). A graph G is tight if it has exactly m(G) vertices of degree (m(G)-1), and any other vertex has degree at most (m(G)-2). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least (m(G)-1) and characterize the graphs G such that (b(G)=m(G)). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in (mathcal {B}_{m}) is m or (m-1) where (mathcal {B}_{m}) is the class of tight bipartite graphs ((D,D{^prime })) of girth 6 such that D is the set of vertices of degree (m-1). We verify the conjecture of Lin and Chang for some subclass of (mathcal {B}_{m}), and we give a lower bound for any graph in (mathcal {B}_{m}).