Bounds for the bb-chromatic number of G−vG−v

The bb-chromatic number of a graph GG is defined as the maximum number kk of colors in a proper coloring to the vertices of GG 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 GG on n≥5n≥5 vertices and any v∈V(G)v∈V(G), b(G)−(⌈n2⌉−2)≤b(G−v)≤b(G)+⌊n2⌋−2. Further we determine all the graphs which attain these bounds.

► Investigation on the bb-chromatic number of vertex-deleted subgraphs. ► For any connected graph GG on n≥5n≥5 vertices and any v∈V(G)v∈V(G), b(G)−(⌈n2⌉−2)≤b(G−v)≤b(G)+⌊n2⌋−2. ► All the graphs which attain these 2 bounds are also determined.