Advances and Applications in Discrete Mathematics

The Advances and Applications in Discrete Mathematics is a prestigious peer-reviewed journal indexed in the Emerging Sources Citation Index (ESCI). It is dedicated to publishing original research articles in the field of discrete mathematics and combinatorics, including topics such as graphs, coding theory, and block design. The journal emphasizes efficient and powerful tools for real-world applications and welcomes expository articles that highlight current developments in the field.

Submit Article

RESULTS ON GRUNDY CHROMATIC NUMBER OF JOIN GRAPH OF GRAPHS

Authors

  • R. Stella Maragatham
  • A. Subramanian

DOI:

https://doi.org/10.17654/0974165823058

Abstract

The Grundy number of a graph G, denoted by $\Gamma(G)$ 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.

Received: February 11, 2023
Revised: May 16, 2023
Accepted: June 6, 2023

References

Y. Caro, A. Sebö and M. Tarsi, Recognizing greedy structures, J. Algorithms 20 (1996), 137-156.

C. A. Christen and S. M. Selkow, Some perfect coloring properties of graphs, J. Combin. Theory Ser. B 27 (1979), 49-59.

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.

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.

N. Goyal and S. Vishvanathan, NP-completeness of undirected Grundy numbering and related problems, Manuscript, Bombay, 1997.

A. Gyárfás and J. Lehel, On-line and first-fit coloring of graphs, J. Graph Theory 12 (1988), 217-227.

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.

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.

T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley, New York, 1995.

G. J. Simmons, On the achromatic number of a graph, Congr. Numer. 40 (1983), 339-366.

J. A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997), 529-550.

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.

M. Zaker, Grundy chromatic number of the complement of bipartite graphs, Australas. J. Combin. 31 (2005), 325-329.

Downloads

Published

2023-07-29

Issue

Vol. 40 No. 1 (2023)

Section

Articles

License

Copyright (c) 2023 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

_________________________

Licensing Terms:

Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.

Contact Pushpa Publishing House for more info or permissions.

How to Cite

RESULTS ON GRUNDY CHROMATIC NUMBER OF JOIN GRAPH OF GRAPHS. (2023). Advances and Applications in Discrete Mathematics, 40(1), 87-100. https://doi.org/10.17654/0974165823058