Abstract: The Grundy number of a graph G, denoted by is the largest k such that G has a greedy k-coloring, that is a coloring with k colors obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we obtain the Grundy chromatic number of join graph of path graph, complete bipartite graph, fan graph, cycle graph, complete graph, wheel graph and gear graph.
|
Keywords and phrases: graph coloring, chromatic number, Grundy coloring, Grundy chromatic number.
Received: February 11, 2023; Revised: May 16, 2023; Accepted: June 6, 2023; Published: July 29, 2023
How to cite this article: R. Stella Maragatham and A. Subramanian, Results on Grundy chromatic number of join graph of graphs, Advances and Applications in Discrete Mathematics 40(1) (2023), 87-100. http://dx.doi.org/10.17654/0974165823058
This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License
References [1] Y. Caro, A. Sebö and M. Tarsi, Recognizing greedy structures, J. Algorithms 20 (1996), 137-156. [2] C. A. Christen and S. M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory Ser. B 27 (1979), 49-59. [3] P. Erdös, W. R. Hare, S. T. Hedetniemi and R. Laskar, On the equality of Grundy and achromatic number of graphs, J. Graph Theory 11 (1987), 157-159. [4] Z. Füredi, A. Gyárfás, G. Sárközy and S. Selkow, Inequalities for the first-fit chromatic number, J. Graph Theory 59(1) (2008), 75-88. [5] N. Goyal and S. Vishvanathan, NP-completeness of undirected Grundy numbering and related problems, Manuscript, Bombay, 1997. [6] A. Gyárfás and J. Lehel, On-line and first-fit coloring of graphs, J. Graph Theory 12 (1988), 217-227. [7] S. M. Hedetniemi, S. T. Hedetniemi and A. Beyer, A linear algorithm for the Grundy (coloring) number of a tree, Congr. Numer. 36 (1982), 351-363. [8] D. G. Hoffman and P. D. Johnson Jr., Greedy colorings and the Grundy chromatic number of the n-cube, Bull. Inst. Combin. Appl. 26 (1999), 49-57. [9] T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley, New York, 1995. [10] G. J. Simmons, On the achromatic number of a graph, Congr. Numer. 40 (1983), 339-366. [11] J. A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997), 529-550. [12] J. Vernold Vivin and K. Kaliraj, On equitable coloring of corona of wheels, Electronic Journal of Graph Theory and Applications 4(2) (2016), 206-222. [13] M. Zaker, Grundy chromatic number of the complement of bipartite graphs, Australas. J. Combin. 31 (2005), 325-329.
|