\(b\)-coloring of the Mycielskian of some classes of graphs (Q2118233)

Let \(G=(V,E)\) be a simple, finite, undirected graph. A \(b\)-coloring of \(G\) using \(k\) colors is a proper coloring of \(V\) in which each color class contains a vertex that is adjacent to a vertex of each other color class. The \(b\)-chromatic number \(b(G)\) of \(G\) is the largest \(k\) such that \(G\) has a \(b\)-coloring using \(k\) colors. For the Mycielskian \(\mu(G)\) of a \(k\)-regular graph \(G\) (\(k \geq 3\)) with girth at least 7 or with girth 5 having diameter at least 5 but not containing a \(C_{6}\), the authors show that \(b(\mu(G))=2k+1=2b(G)-1\). If \(G\) is of girth at least 6, they show that \(k+ \lfloor \frac{k+1}{2} \rfloor \leq b(\mu(G)) \leq 2k+1\), and if \(G\) is of girth at least 8, then \(\mu(G))\) is \(b\)-continuous. They also determine the \(b\)-chromatic number of the Mycielskian of split graphs and graphs with \(b(G)=2\). They conclude with some results on the \(b\)-chromatic number of the generalized Mycielskian of some families of regular graphs.