Injective edge colorings of degenerate graphs and the oriented chromatic number

Abstract

Given a graph $G$, an injective edge-coloring of $G$ is a function $\psi :E(G)\to \mathbb{N}$ such that if $\psi (e)=\psi (e^{\prime })$, then no third edge joins an endpoint of $e$ and an endpoint of $e^{\prime }$. The injective chromatic index of a graph $G$, written ${\chi }_{inj}^{\prime }(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 $\Delta$, then ${\chi }_{inj}^{\prime }(G)=O(d^3\log \Delta )$. Next, we show that if $G$ is a graph of Euler genus $g$, then ${\chi }_{inj}^{\prime }(G)\le (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^{\frac{1}{2}+\epsilon })}$ and resolving a conjecture of Aravind and Subramanian.

18 pages