b-Coloring of the Mycielskian of Some Classes of Graphs

Abstract

The b-chromatic number b(G) of a graph G is the maximum k for which G has a proper vertex coloring using k colors such that each color class contains at least one vertex adjacent to a vertex of every other color class. In this paper, we have mainly investigated on the b-chromatic number of the Mycielskian of regular graphs. In particular, we have obtained the exact value of the b-chromatic number of the Mycielskian of some classes of graphs. This includes a few families of regular graphs, graphs with b(G) = 2 and split graphs. In addition, we have found bounds for the b-chromatic number of the Mycielskian of some more families of regular graphs in terms of the bchromatic number of their original graphs. Also we have found b-chromatic number of the generalized Mycielskian of some regular graphs.

Keywords

• b-coloring
• b-chromatic number
• mycielskian of graphs
• regular graphs
• 05c15