Grundy number of corona product of some graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-4962Keywords:
grundy number, corona product, 2-regular graph, cycle, complete bipartite, ladder graph, fan graphAbstract
The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex u colored with color i, 1 ≤ i ≤ k, is adjacent to i – 1 vertices colored with each color j, 1 ≤ j ≤ i − 1. In this paper we obtain the Grundy number of corona product of some graphs, denoted by G ◦ H. First, we consider the graph G be 2-regular graph and H be a cycle, complete bipartite, ladder graph and fan graph. Also we consider the graph G and H be a complete bipartite graphs, fan graphs.
References
C. Berge, Graphs and Hypergraphs. North Holland, 1973.
Y. Caro, A. Sebö and M. Tarsi, “Recognizing greedy structures”, Journal of Algorithms, vol. 20, no. 1, pp. 137-156, 1996. https://doi.org/10.1006/jagm.1996.0006
C.A. Christen and S.M. Selkow, “Some perfect coloring properties of graphs”, Journal of Combinatorial Theory, Series B, vol. 27, no. 1, pp. 49-59, 1979. https://doi.org/10.1016/0095-8956(79)90067-4
J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, R.C. Laskar and D.F. Rall, “Fall Colorings of Graphs”, Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 33, pp. 257-273, 2000.
P. Erdös, W.R. Hare, S.T. Hedetniemi and R. Laskar, “On the equality of Grundy and ochromatic number of graphs”, Journal of Graph Theory, vol. 11, pp. 157-159, 1987.
R. Frucht and F. Harary, “On the corona of two graphs”, Aequationes Mathematicae, vol. 4, pp. 322-325, 1970. https://doi.org/10.1007/BF01844162
Z. Füredi, A. Gyárfás, G. Sárközy and S. Selkow, “Inequalities for the First-Fit chromatic number”, Journal of Graph Theory, vol. 59, no. 1, pp. 75-88, 2008.
M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman, 1979.
C. Germain and H. Kheddouci, “Grundy coloring for power graphs”, Electronic Notes in Discrete Mathematics, vol. 15, pp. 65-67, 2004. https://doi.org/10.1016/S1571-0653(04)00533-5
N. Goyal and S. Vishvanathan, NP-completeness of undirected Grundy numbering and related problems. Manuscript, Bombay, 1997.
P. M. Grundy, “Mathematics and games”, Eureka, vol. 2, pp. 6-8, 1939.
A. Gyárfás and J. Lehel, “On-line and first-fit coloring of graphs”, Journal of Graph Theory, vol. 12, pp. 217-227, 1988. https://doi.org/10.1002/jgt.3190120212
F. Harary, Graph Theory. New Delhi: Narosa Publishing home, 1969.
K. Kaliraj, R. Sivakami and J. Vernold Vivin, “Star Edge Coloring of Corona Product of Path with Some Graphs”, International Journal of Mathematical Combinatorics, vol. 3, pp. 115-122, 2016.
K. Kaliraj, R. Sivakami and J. Vernold Vivin, “Star edge coloring of corona product of path and wheel graph families”, Proyecciones (Antofagasta), vol. 37, no. 4, pp. 593-601, 2018. https://doi.org/10.4067/S0716-09172018000400593
A. Mansouri and M.S. Bouhlel, “A Linear Algorithm for the Grundy Number of A Tree”, International Journal of Computer Science and Information Technology, vol. 6, no. 1, pp. 155-160, 2014. https://doi.org/10.5121/ijcsit.2014.6112
C. Parks and J. Rhyne, Grundy Coloring for Chessboard Graphs. Seventh North Carolina Mini-Conference on Graph Theory, Combinatorics, and Computing, 2002.
P. Sumathi and A. Rathi, “Quotient labeling of some ladder graphs”, American Journal of Engineering Research, vol. 7, no. 12, pp. 38-42, 2018.
J.A. Telle and A. Proskurowski, “Algorithms for Vertex Partitioning Problems on Partial k-Trees”, SIAM Journal on Discrete Mathematics, vol. 10, no. 4, pp. 529-550, 1997. https://doi.org/10.1137/S0895480194275825
J. Vernold Vivin and K. Kaliraj, “On equitable coloring of corona of wheels”, Electronic Journal of Graph Theory and Applications, vol. 4, no. 2, pp. 206-222, 2016.
J. Vernold Vivin and M. Venkatachalam, “A Note on b-Coloring of Fan Graphs”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 17, nos. 5-6, pp. 443-448, 2014. https://doi.org/10.1080/09720529.2013.876781
J. Vernold Vivin, Harmonious Coloring of total graph, n-leaf, central graphs and Circumdetic graphs. Bharathiyar University, Ph.D Thesis, Coimbatore, India, 2007.
M. Zaker, “Grundy chromatic number of the complement of bipartite graphs”, Australasian Journal of Combinatorics, vol. 31, pp. 325-329, 2005.
Published
How to Cite
Issue
Section
Copyright (c) 2023 R. Stella Maragatham, A. Subramanian
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
