On Acyclic Coloring of Mycielskians

Kaliraj K., Kowsalya V., Vernold Vivin J.

Abstract


An acyclic coloring of a graph \(G\) is a proper vertex coloring such that the induced subgraph of any two color classes is acyclic. The minimum number of colors needed to acyclically color the vertices of a graph \(G\) is called as acyclic chromatic number and is denoted by \(\chi_a(G)\). In this paper, we give the exact value of the acyclic chromatic number of Mycielskian graph of cycles, paths, complete graphs and complete bipartite graphs.

Keywords


Acyclic coloring; Mycielskian

Full Text:

PDF

References


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. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973), 390 – 408.

F. Harary, Graph Theory, Narosa Publishing House, New Delhi (1969).

J. Miškuf, R. Škrekovski 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.




DOI: http://dx.doi.org/10.26713%2Fjims.v9i3.949

eISSN 0975-5748; pISSN 0974-875X