Multicoloring the Mycielskian of Graphs
GuanFeng Ren, Yuehua Bu · 2008
A k-fold coloring of a graph G is an assignment of k distinct colors to each vertex of G so that adjacent vertices receive no colors in common. The k-th chromatic number of G,denote by chik(G), is the smallest number of colors needed to give G a k-fold coloring. Let mup(G) denote the p-Mycielskian of G. In this paper, we show that chik(mu(Wn)) = 3k + [k/3] + 1 (n is even, n ges 2k + 2 > 4). Moreover, we investigate the k-th chromatic number of Mycielskians of bipartite graph. Finally, we determine the values of chik(mup(G)) (chi(G) = omega(G) = n ges 3).