Bounds for the b-chromatic number of the Mycielskian of some families of graphs

The b-chromatic number b(G) of a graph G is defined as the maximum number k of colors in a proper coloring of 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. Let mu(G) denote the Mycielskian of G. In this paper, it is shown that if G is a graph with b-chromatic number b and for which the number of vertices of degree at least b is at most 2b - 2, then b(mu(G)) lies in the interval [b+1, 2b-1]. As a consequence, it follows that b(G) +1 <= b(mu(G)) <= 2b(G)-1 for G in any of the following families: split graphs, K-k,K-k - {a 1-factor}, the hypercubes Q(p), where p >= 3, trees and a special class of bipartite graphs. We show further that for any positive integer b and every integer k is an element of [b + 1, 2b - 1], there exists a graph G belonging to the family mentioned above, with b(G) = b and b(mu(G)) = k.