Abstract:
Graph theory is a branch of mathematics that studies how objects are connected using vertices
and edges. An important concept within this field is incidence coloring, where colors are
assigned to vertex edge pairs, called incidences, rather than to vertices or edges alone. The
minimum number of colors required to ensure that no two adjacent incidences receive the same
color is known as the incidence chromatic number, denoted by χi(G). This research introduces
the Recursive Modified Claw Graph, constructed from a four-edge base graph with one
central vertex of degree four with four leaves. The graph is expanded level by level attaching
new duplicates of the base graph to the leaves created in the previous level according to a
fixed recursive pattern, while maximum degree remains four. The general structure (Gn) has
V(n) = 6×3n−1 −1 vertices and E(n) = 6×3n−1 −2 edges for all n ≥ 1, where n ∈ Z+. A
cycling five color palette is introduced by rotating a level color cn through {1,2,3,4,5} while
each new center vertex uses the remain four colors, and all new leaf-side incidences use cn. An
induction proof shows this always gives a proper incidence coloring with χi(Gn) ≤ 5 for all
n ≥ 1 with potential applications in areas such as timetable scheduling, network optimization
and resource allocation, where conflict-free assignments are essential. This work extends existing
incidence coloring theory beyond trees and standard cactus graphs to structured claw-based
recursive families, contributing both theoretical insights and a scalable algorithmic framework.
