Bounds for b-chromatic number of subgraphs and edge-deleted subgraphs
P. Francis, S. Francis Raj · Discussiones Mathematicae Graph Theory · 2016
A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes.The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G.In this paper, we obtain bounds for the bchromatic number of induced subgraphs in terms of the b-chromatic number of the original graph.This turns out to be a generalization of the result due to R. Balakrishnan et al. [Bounds for the b-chromatic number of Gv, Discrete Appl.Math.161 (2013) 1173-1179].Also we show that for any connected graph G and any e ∈ E(G), b(Ge) ≤ b(G) + n2 -2.Further, we determine all graphs which attain the upper bound.Finally, we conclude by finding bound for the b-chromatic number of any subgraph.