Bounds for the b b -chromatic number of G?v G ? v
The b b -chromatic number of a graph G G is defined as the maximum number k k of colors in a proper coloring to the vertices of G G in such a way that each color class contains at least one vertex adjacent to a vertex of every other color class. In this paper, we show that for any connected graph G G on n?5 n ? 5 vertices and any v?V(G) v ? V ( G ) , b ( G ) ? ( ? n 2 ? ? 2 ) ? b ( G ? v ) ? b ( G ) + ? n 2 ? ? 2 . Further we determine all the graphs which attain these bounds.
b-chromatic number