Injective edge colorings of degenerate graphs and the oriented chromatic number
PETER L. BRADSHAW, Alexander Clow, Jingwei Xu · European Journal of Combinatorics · 2025
Given a graph G , an injective edge-coloring of G is a function ψ : E ( G ) → N such that if ψ ( e ) = ψ ( e ′ ) , then no third edge joins an endpoint of e and an endpoint of e ′ . The injective chromatic index of a graph G , written χ inj ′ ( G ) , is the minimum number of colors needed for an injective edge coloring of G . In this paper, we investigate the injective chromatic index of certain classes of degenerate graphs. First, we show that if G is a d -degenerate graph of maximum degree Δ , then χ inj ′ ( G ) = O ( d 3 log Δ ) . Next, we show that if G is a graph of Euler genus g , then χ inj ′ ( G ) ≤ ( 3 + o ( 1 ) ) g , which is tight when G is a clique. Finally, we show that the oriented chromatic number of a graph is at most exponential in its injective chromatic index. Using this fact, we prove that the oriented chromatic number of a graph embedded on a surface of Euler genus g has oriented chromatic number at most O ( g 6400 ) , improving the previously known upper bound of 2 O ( g 1 2 + ɛ ) and resolving a conjecture of Aravind and Subramanian.