Bounds for the b-chromatic number of G - v

The b-chromatic number of a graph G is defined as the maximum number k of colors in a proper coloring to the vertices of 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 on n >= 5 vertices and any v is an element of V (G), b(G) - (inverted right perpendicular n/2 inverted left perpendicular - 2) <= b(G - v) <= b(G) + left perpendicular n/2 right perpendicular - 2. Further we determine all the graphs which attain these bounds. (c) 2011 Elsevier B.V. All rights reserved.