Five-color incidence coloring of the recursive modified claw graph

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.