Back to Search
Start Over
Injective edge colorings of degenerate graphs and the oriented chromatic number
- Publication Year :
- 2023
-
Abstract
- Given a graph $G$, an injective edge-coloring of $G$ is a function $\psi:E(G) \rightarrow \mathbb N$ such that if $\psi(e) = \psi(e')$, then no third edge joins an endpoint of $e$ and an endpoint of $e'$. The injective chromatic index of a graph $G$, written $\chi_{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 $\Delta$, then $\chi_{inj}'(G) = O(d^3 \log \Delta)$. Next, we show that if $G$ is a graph of Euler genus $g$, then $\chi_{inj}'(G) \leq (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.<br />Comment: 18 pages
- Subjects :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2308.15654
- Document Type :
- Working Paper