On the bb-coloring of G−eG−e

The bb-chromatic number of a graph GG is the largest integer kk such that GG has a coloring of the vertices in kk color classes such that every color class contains a vertex that has a neighbor in all other color classes. In this paper, we show that for every edge ee of a graph GG, we have b(G−e)≤b(G)+⌈n2⌉−2. Also, we characterize all graphs GG for which b(G−e)=b(G)+⌈n2⌉−2 for some edge ee of GG.