Results on Grundy Edge Coloring of Some Special Graphs

Kailasam Annathurai; Ponpandi Periasamy; Vaithilingam Sankar Raj

doi:doi:10.11648/j.ajam.20261406.11

Research Article |

| Peer-Reviewed

Results on Grundy Edge Coloring of Some Special Graphs

Kailasam Annathurai^*

, Ponpandi Periasamy

, Vaithilingam Sankar Raj

Published in American Journal of Applied Mathematics (Volume 14, Issue 6)

Received: 6 September 2026 Accepted: 29 September 2026 Published: 4 November 2026

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

An edge coloring of a simple, connected, undirected graph G is an assignment of color labels to the edges of G such that no two adjacent edges are assigned the same color. The first-fit or greedy edge coloring algorithm colors edges sequentially by assigning the smallest available positive integer color to each edge. The Grundy edge chromatic number, denoted by Γ'(G), captures the worst-case performance of this greedy approach, defined formally as the maximum number of colors utilized by the greedy edge coloring algorithm across all possible orderings of the edge set E(G). Determining Γ'(G) is known to be computationally hard in general, prompting significant research into deriving exact values and structural bounds for specialized graph families and graph operations. In this paper, we explore the Grundy edge chromatic number for several key topological families and structured composite graphs. First, we focus on the shadow graph operation, denoted D₂(G), which duplicates the vertex set of G and interconnects vertices based on their neighborhood adjacencies. We establish exact explicit formulas for the Grundy edge chromatic number of shadow graphs constructed from foundational graph structures, including paths P_n, cycles C_n, sunlet graphs S_n, and tadpole graphs T_n,k. Second, we extend our investigation to complex wheel-like and symmetric network architectures. Specifically, we evaluate the structural properties and derive exact closed-form expressions for the Grundy edge chromatic number of closed helm graphs CH_n, double wheel graphs DW_n, and djembe graphs D_n. For each considered graph class, we construct explicit edge orderings that force the greedy algorithm to attain its theoretical upper bound, thereby matching the structural upper bounds derived from degree conditions and neighborhood characteristics. These exact results provide comprehensive insights into the performance bounds of greedy edge-labeling heuristics in interconnection networks, expanding the current understanding of greedy coloring parameters in graph theory.

Published in	American Journal of Applied Mathematics (Volume 14, Issue 6)
DOI	10.11648/j.ajam.20261406.11
Page(s)	389-400
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2026. Published by Science Publishing Group

Keywords

Grundy Edge Chromatic Number, Shadow Graph, Sunlet, Tadpole Graph, Closed Helm Graph, Double Wheel Graph, Djembe Graph

References

[1]	Annathurai, K., Periasamy, P., Sankar Raj, V. Results on the Grundy Chromatic Number of Prism Graphs. Statistics, Optimization and Information Computing. 2026, 15, 1810–1820. https://doi.org/10.19139/soic-2310-5070-3093
[2]	Annathurai, K., Periasamy, P., Sankar Raj, V. Results on Grundy Number of Fan Graph Families. Communications on Applied Nonlinear Analysis. 2024, 31(8s), 1194–1199. https://doi.org/10.52783/cana.v31.6080
[3]	Annathurai, K., Periasamy, P., Sankar Raj, V. Grundy Edge Coloring of Shadow Graph of Some Graphs. International Journal of Applied Mathematics. 2025, 38(9s), 1221–1236. https://doi.org/10.12732/ijam.v38i9s.850
[4]	Brandt, S., Foerster, K.-T., Maurer, J., Wattenhofer, R. Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs. Theoretical Computer Science. 2020, 839, 176–185. https://doi.org/10.48550/arXiv.1903.00581
[5]	Caro, Y., Sebö, A., Tarsi, M. Recognizing Greedy Structures. Journal of Algorithms. 1996, 20, 137–156. https://api.semanticscholar.org/CorpusID:43281475
[6]	Christen, C. A., Selkow, S. M. Some Perfect Coloring Properties of Graphs. Journal of Combinatorial Theory, Series B. 1979, 27, 49–59. https://doi.org/10.1016/0095-8956(79)90067-4
[7]	Erdös, P., Hare, W. R., Hedetniemi, S. T., Laskar, R. On the Equality of Grundy and Ochromatic Number of Graphs. Journal of Graph Theory. 1987, 11, 157–159. https://doi.org/10.1016/S0012-365X(03)00184-5
[8]	Füredi, Z., Gyárfás, A., Sárközy, G., Selkow, S. Inequalities for the First-Fit Chromatic Number. Journal of Graph Theory. 2008, 59(1), 75–88. https://doi.org/10.1002/jgt.20327
[9]	Gyárfás, A., Lehel, J. On-line and First-Fit Coloring of Graphs. Journal of Graph Theory. 1988, 12, 217–227. https://doi.org/10.1002/jgt.3190120212
[10]	Harary, F., Frick, M. On the Construction of Shadow Graphs. Congressus Numerantium. 1994, 98, 73–80.
[11]	Hedetniemi, S. M., Hedetniemi, S. T., Beyer, A. A Linear Algorithm for the Grundy (Coloring) Number of a Tree. Congressus Numerantium. 1982, 36, 351–363.
[12]	Hoffman, D. G., Johnson Jr., P. D. Greedy Colorings and the Grundy Chromatic Number of the n-Cube. Bulletin of the Institute of Combinatorics and its Applications. 1999, 26, 49–57.
[13]	Jensen, T. R., Toft, B. Graph Coloring Problems. Wiley, New York; 1995. https://doi.org/10.5860/CHOICE.32-6283
[14]	Kaliraj, K., Narmadha Devi, R., Vernold Vivin, J. Equitable Chromatic Number of Weak Modular Product of Some Graphs. Proyecciones Journal of Mathematics (Antofagasta). 2022, 41(5), 1051–1062. https://doi.org/10.22199/issn.0717-6279-5140
[15]	Kaliraj, K., Vernold Vivin, J., Tamilselvan, G. T. On r-Hued Coloring of Corona Product of Some Graphs. Missouri Journal of Mathematical Sciences. 2024, 36(1), 121–129. https://doi.org/10.35834/2024/3601121
[16]	Kaliraj, K., Vernold Vivin, J., Akbar Ali, M. M. On Equitable Coloring of Sunlet Graph Families. Utilitas Mathematica. 2012, 103, 497–504.
[17]	Ellumkalayil, M. T., Naduvath, S. On δ(k)-Coloring of Powers of Helm and Closed Helm Graphs. Discrete Mathematics, Algorithms and Applications. 2022, 14(2), Article ID: 2150116. https://doi.org/10.1142/S1793830921501160
[18]	Rao, S. B., Somasundaram, S. Properties of Shadow Graphs. Indian Journal of Mathematics. 2006, 48(2), 241–250.
[19]	Rohini, A., Venkatachalam, M. On Irregular Colorings of Double Wheel Graph Families. Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics. 2019, 68(1), 944–949. https://doi.org/10.31801/cfsuasmas.000000
[20]	Susanth, C., Sudev, N. K., Kalayathankal, S. J. On Chromatic Curling Number of Graphs. Contemporary Studies in Discrete Mathematics. 2017, 1(1), 21–30. https://doi.org/10.48550/arXiv.1804.01860
[21]	Vaidya, S., Kanani, A. Grundy Edge Colorings of Some Derived Graphs. International Journal of Computer Applications. 2017, 167(12), 16–20.
[22]	Vivin, J. V., Kaliraj, K. On Equitable Coloring of Corona of Wheels. Electronic Journal of Graph Theory and Applications. 2016, 4(2), 206–222. https://doi.org/10.5614/ejgta.2016.4.2.8
[23]	Zaker, M. Grundy Chromatic Number of the Complement of Bipartite Graphs. Australasian Journal of Combinatorics. 2005, 31, 325–329. https://ajc-new.maths.uq.edu.au/v31.p325

Cite This Article

Plain Text BibTeX RIS

APA Style

Annathurai, K., Periasamy, P., Raj, V. S. (2026). Results on Grundy Edge Coloring of Some Special Graphs. American Journal of Applied Mathematics, 14(6), 389-400. https://doi.org/10.11648/j.ajam.20261406.11

Copy | Download

ACS Style

Annathurai, K.; Periasamy, P.; Raj, V. S. Results on Grundy Edge Coloring of Some Special Graphs. Am. J. Appl. Math. 2026, 14(6), 389-400. doi: 10.11648/j.ajam.20261406.11

Copy | Download

AMA Style

Annathurai K, Periasamy P, Raj VS. Results on Grundy Edge Coloring of Some Special Graphs. Am J Appl Math. 2026;14(6):389-400. doi: 10.11648/j.ajam.20261406.11

Copy | Download

@article{10.11648/j.ajam.20261406.11,
  author = {Kailasam Annathurai and Ponpandi Periasamy and Vaithilingam Sankar Raj},
  title = {Results on Grundy Edge Coloring of Some Special Graphs},
  journal = {American Journal of Applied Mathematics},
  volume = {14},
  number = {6},
  pages = {389-400},
  doi = {10.11648/j.ajam.20261406.11},
  url = {https://doi.org/10.11648/j.ajam.20261406.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20261406.11},
  abstract = {An edge coloring of a simple, connected, undirected graph G is an assignment of color labels to the edges of G such that no two adjacent edges are assigned the same color. The first-fit or greedy edge coloring algorithm colors edges sequentially by assigning the smallest available positive integer color to each edge. The Grundy edge chromatic number, denoted by Γ'(G), captures the worst-case performance of this greedy approach, defined formally as the maximum number of colors utilized by the greedy edge coloring algorithm across all possible orderings of the edge set E(G). Determining Γ'(G) is known to be computationally hard in general, prompting significant research into deriving exact values and structural bounds for specialized graph families and graph operations. In this paper, we explore the Grundy edge chromatic number for several key topological families and structured composite graphs. First, we focus on the shadow graph operation, denoted D2(G), which duplicates the vertex set of G and interconnects vertices based on their neighborhood adjacencies. We establish exact explicit formulas for the Grundy edge chromatic number of shadow graphs constructed from foundational graph structures, including paths Pn, cycles Cn, sunlet graphs Sn, and tadpole graphs Tn,k. Second, we extend our investigation to complex wheel-like and symmetric network architectures. Specifically, we evaluate the structural properties and derive exact closed-form expressions for the Grundy edge chromatic number of closed helm graphs CHn, double wheel graphs DWn, and djembe graphs Dn. For each considered graph class, we construct explicit edge orderings that force the greedy algorithm to attain its theoretical upper bound, thereby matching the structural upper bounds derived from degree conditions and neighborhood characteristics. These exact results provide comprehensive insights into the performance bounds of greedy edge-labeling heuristics in interconnection networks, expanding the current understanding of greedy coloring parameters in graph theory.},
 year = {2026}
}

Copy | Download

TY  - JOUR
T1  - Results on Grundy Edge Coloring of Some Special Graphs
AU  - Kailasam Annathurai
AU  - Ponpandi Periasamy
AU  - Vaithilingam Sankar Raj
Y1  - 2026/11/04
PY  - 2026
N1  - https://doi.org/10.11648/j.ajam.20261406.11
DO  - 10.11648/j.ajam.20261406.11
T2  - American Journal of Applied Mathematics
JF  - American Journal of Applied Mathematics
JO  - American Journal of Applied Mathematics
SP  - 389
EP  - 400
PB  - Science Publishing Group
SN  - 2330-006X
UR  - https://doi.org/10.11648/j.ajam.20261406.11
AB  - An edge coloring of a simple, connected, undirected graph G is an assignment of color labels to the edges of G such that no two adjacent edges are assigned the same color. The first-fit or greedy edge coloring algorithm colors edges sequentially by assigning the smallest available positive integer color to each edge. The Grundy edge chromatic number, denoted by Γ'(G), captures the worst-case performance of this greedy approach, defined formally as the maximum number of colors utilized by the greedy edge coloring algorithm across all possible orderings of the edge set E(G). Determining Γ'(G) is known to be computationally hard in general, prompting significant research into deriving exact values and structural bounds for specialized graph families and graph operations. In this paper, we explore the Grundy edge chromatic number for several key topological families and structured composite graphs. First, we focus on the shadow graph operation, denoted D2(G), which duplicates the vertex set of G and interconnects vertices based on their neighborhood adjacencies. We establish exact explicit formulas for the Grundy edge chromatic number of shadow graphs constructed from foundational graph structures, including paths Pn, cycles Cn, sunlet graphs Sn, and tadpole graphs Tn,k. Second, we extend our investigation to complex wheel-like and symmetric network architectures. Specifically, we evaluate the structural properties and derive exact closed-form expressions for the Grundy edge chromatic number of closed helm graphs CHn, double wheel graphs DWn, and djembe graphs Dn. For each considered graph class, we construct explicit edge orderings that force the greedy algorithm to attain its theoretical upper bound, thereby matching the structural upper bounds derived from degree conditions and neighborhood characteristics. These exact results provide comprehensive insights into the performance bounds of greedy edge-labeling heuristics in interconnection networks, expanding the current understanding of greedy coloring parameters in graph theory.
VL  - 14
IS  - 6
ER  -

Copy | Download

Author Information

Kailasam Annathurai

Department of Mathematics, Thiruvalluvar College, Papanasam, India

Contact Email

http://orcid.org/0009-0003-8631-9388
Ponpandi Periasamy

Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli, India

Contact Email

http://orcid.org/0000-0001-7971-7909
Vaithilingam Sankar Raj

Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli, India

Contact Email

http://orcid.org/0000-0001-6912-4712

Download PDF

Submit an Article

Sections

Plain Text BibTeX RIS

APA Style

Annathurai, K., Periasamy, P., Raj, V. S. (2026). Results on Grundy Edge Coloring of Some Special Graphs. American Journal of Applied Mathematics, 14(6), 389-400. https://doi.org/10.11648/j.ajam.20261406.11

Copy | Download

ACS Style

Annathurai, K.; Periasamy, P.; Raj, V. S. Results on Grundy Edge Coloring of Some Special Graphs. Am. J. Appl. Math. 2026, 14(6), 389-400. doi: 10.11648/j.ajam.20261406.11

Copy | Download

AMA Style

Annathurai K, Periasamy P, Raj VS. Results on Grundy Edge Coloring of Some Special Graphs. Am J Appl Math. 2026;14(6):389-400. doi: 10.11648/j.ajam.20261406.11

Copy | Download

@article{10.11648/j.ajam.20261406.11,
  author = {Kailasam Annathurai and Ponpandi Periasamy and Vaithilingam Sankar Raj},
  title = {Results on Grundy Edge Coloring of Some Special Graphs},
  journal = {American Journal of Applied Mathematics},
  volume = {14},
  number = {6},
  pages = {389-400},
  doi = {10.11648/j.ajam.20261406.11},
  url = {https://doi.org/10.11648/j.ajam.20261406.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20261406.11},
  abstract = {An edge coloring of a simple, connected, undirected graph G is an assignment of color labels to the edges of G such that no two adjacent edges are assigned the same color. The first-fit or greedy edge coloring algorithm colors edges sequentially by assigning the smallest available positive integer color to each edge. The Grundy edge chromatic number, denoted by Γ'(G), captures the worst-case performance of this greedy approach, defined formally as the maximum number of colors utilized by the greedy edge coloring algorithm across all possible orderings of the edge set E(G). Determining Γ'(G) is known to be computationally hard in general, prompting significant research into deriving exact values and structural bounds for specialized graph families and graph operations. In this paper, we explore the Grundy edge chromatic number for several key topological families and structured composite graphs. First, we focus on the shadow graph operation, denoted D2(G), which duplicates the vertex set of G and interconnects vertices based on their neighborhood adjacencies. We establish exact explicit formulas for the Grundy edge chromatic number of shadow graphs constructed from foundational graph structures, including paths Pn, cycles Cn, sunlet graphs Sn, and tadpole graphs Tn,k. Second, we extend our investigation to complex wheel-like and symmetric network architectures. Specifically, we evaluate the structural properties and derive exact closed-form expressions for the Grundy edge chromatic number of closed helm graphs CHn, double wheel graphs DWn, and djembe graphs Dn. For each considered graph class, we construct explicit edge orderings that force the greedy algorithm to attain its theoretical upper bound, thereby matching the structural upper bounds derived from degree conditions and neighborhood characteristics. These exact results provide comprehensive insights into the performance bounds of greedy edge-labeling heuristics in interconnection networks, expanding the current understanding of greedy coloring parameters in graph theory.},
 year = {2026}
}

Copy | Download

TY  - JOUR
T1  - Results on Grundy Edge Coloring of Some Special Graphs
AU  - Kailasam Annathurai
AU  - Ponpandi Periasamy
AU  - Vaithilingam Sankar Raj
Y1  - 2026/11/04
PY  - 2026
N1  - https://doi.org/10.11648/j.ajam.20261406.11
DO  - 10.11648/j.ajam.20261406.11
T2  - American Journal of Applied Mathematics
JF  - American Journal of Applied Mathematics
JO  - American Journal of Applied Mathematics
SP  - 389
EP  - 400
PB  - Science Publishing Group
SN  - 2330-006X
UR  - https://doi.org/10.11648/j.ajam.20261406.11
AB  - An edge coloring of a simple, connected, undirected graph G is an assignment of color labels to the edges of G such that no two adjacent edges are assigned the same color. The first-fit or greedy edge coloring algorithm colors edges sequentially by assigning the smallest available positive integer color to each edge. The Grundy edge chromatic number, denoted by Γ'(G), captures the worst-case performance of this greedy approach, defined formally as the maximum number of colors utilized by the greedy edge coloring algorithm across all possible orderings of the edge set E(G). Determining Γ'(G) is known to be computationally hard in general, prompting significant research into deriving exact values and structural bounds for specialized graph families and graph operations. In this paper, we explore the Grundy edge chromatic number for several key topological families and structured composite graphs. First, we focus on the shadow graph operation, denoted D2(G), which duplicates the vertex set of G and interconnects vertices based on their neighborhood adjacencies. We establish exact explicit formulas for the Grundy edge chromatic number of shadow graphs constructed from foundational graph structures, including paths Pn, cycles Cn, sunlet graphs Sn, and tadpole graphs Tn,k. Second, we extend our investigation to complex wheel-like and symmetric network architectures. Specifically, we evaluate the structural properties and derive exact closed-form expressions for the Grundy edge chromatic number of closed helm graphs CHn, double wheel graphs DWn, and djembe graphs Dn. For each considered graph class, we construct explicit edge orderings that force the greedy algorithm to attain its theoretical upper bound, thereby matching the structural upper bounds derived from degree conditions and neighborhood characteristics. These exact results provide comprehensive insights into the performance bounds of greedy edge-labeling heuristics in interconnection networks, expanding the current understanding of greedy coloring parameters in graph theory.
VL  - 14
IS  - 6
ER  -

Copy | Download