Research Article
Results on Grundy Edge Coloring of Some Special Graphs
Issue:
Volume 14, Issue 6, December 2026
Pages:
389-400
Received:
6 September 2026
Accepted:
29 September 2026
Published:
4 November 2026
DOI:
10.11648/j.ajam.20261406.11
Downloads:
Views:
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.
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 numbe...
Show More
,
Ponpandi Periasamy
