On Achromatic Coloring of Corona Graphs

D. Vijayalakshmi, N. Nithya Devi


Let \(G = (V(G),E(G))\) be a simple graph and an achromatic coloring of \(G\) is a proper vertex coloring of \(G\) in which every pair of colors appears on at least one pair of adjacent vertices. The achromatic number of \(G\) denoted by \(\psi(G)\), is the greatest number of colors in an achromatic coloring of \(G\). In this paper, we find out the achromatic number for Corona graph of Cycle with Path graphs on the same order \(n\), Path with Cycle graphs on the same order \(n\), Path with Complete graphs on the same order \(n\), Path of order \(n\) with Star graph on order \(n+1\), Path with Wheel graphs on the same order \(n\) and Ladder graph with Path graph on the same order \(n\).


Achromatic coloring; Achromatic number; Corona graph

Full Text:



J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, MacMillan, London (1976).

J. Gross and J. Yellen, Handbook of Graph Theory, CRC Press, New York (2004).

F. Harrary and S. Hedetniemi, The achromatic number of graph, Journal of Combinational Theory 8 (1970), 154 – 161.

D.B. West, Introduction to Graph Theory, 2nd edition, Prentice-Hall of India, Private Limited, New Delhi (2006).

K. Thilagavathi, K.P. Thilagavathy and N. Roopesh, The achromatic coloring of graphs, Electronic Notes in Discrete Mathematics 33 (2009), 153 – 156.

K. Venkatesan, V.V.Joseph and V. Mathiyazhagan, On star coloring of corona graphs, Applied Mathematics E-Noted 15 (2015), 97 – 104.

S. Klavzar, R. Hammack and W. Imrich, Handbook of Graph Products, CRC Press (2011).

R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970), 322 – 325.

P. Hell and D.J. Miller, Graphs with given achromatic number, Discrete Mathematics 16 (1976), 195 – 207.

M. Yannakakis and F. Gavril, Edge dominating sets in graphs, SIAM Journal of Applied Mathematics 38 (1980), 364 – 372.

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

eISSN 0975-5748; pISSN 0974-875X