On star coloring of Mycielskians
Abstract
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.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.19184/ijc.2018.2.2.3
References
M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kundgen and R. Ramamurthi, Coloring with no 2-Colored P_4's, The Electronic Journal of Combinatorics 11 (2004), Paper #R26,13.
J. A. Bondy and U. S. R. Murty, Graph theory with Applications, London, MacMillan (1976).
G. J. Chang, L. Huang and X. Zhu, Circular chromatic numbers of Mycielski's graphs, Discrete Math. 205 (1-3) (1999), 23-37.
B. Grunbaum, Acyclic colorings of planar graphs, Israel J.Math. 14 (1973), 390-408.
F. Guillaume, A. Raspaud and B. Reed, On Star coloring of graphs, J. Graph Theory 47 (3) (2004), 163-182.
F. Harary, Graph Theory, Narosa Publishing home, New Delhi (1969).
J. Miskuf, R. Skrekovski, and M. Tancer, Backbone Colorings and generalized Mycielski Graphs, SIAM J. Discrete Math. 23 (2) (2009), 1063-1070.
J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), 161-162.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.