Bounds for the \(b\)-Chromatic Number of the Mycielskian of Some Families of Graphs

Abstract

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 \leq b(\mu(G)) \leq 2b(G) -1\) for \(G\) in any of the following families: split graphs, \(K_{n,n} – \{a \ 1\text{-factor}\}\), the hypercubes \(Q_p\), where \(p \geq 3\), trees, and a special class of bipartite graphs. We show further that for any positive integer \(b\) and every integer \(k \in [b+1, 2b-1]\), there exists a graph \(G\) belonging to the family mentioned above, with \(b(G) = b\) and \(b(\mu(G)) = k\).