On star coloring of Mycielskians

K. Kaliraj (University of Madras)
V. Kowsalya (Bharathiar University)
Vernold Vivin (University College of Engineering Nagercoil)

Indonesian Journal of Combinatorics
Vol 2, No 2 (2018)

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. In this paper, we find the star chromatic number for the Mycielskian graph of complete graphs, paths, cycles and complete bipartite graphs.