Odd graphs and its application on the strong edge coloring.
Tao Wang, Xiaodan Zhao · arXiv (Cornell University) · 2014
A strong edge coloring of a graph is a proper edge coloring in which every color class is an induced matching. The strong chromatic index $\chiup_{s}'(G)$ of a graph $G$ is the minimum number of colors in a strong edge coloring of $G$. Let $\Delta \geq 4$ be an integer. In this note, we study the properties of the odd graphs, and show that every planar graph with maximum degree at most $\Delta$ and girth at least $10 \Delta - 4$ has a strong edge coloring with $2\Delta - 1$ colors. In addition, we prove that if $G$ is a graph with girth at least $2\Delta - 1$ and $\mad(G) < 2 + \frac{1}{3\Delta - 2}$, where $\Delta \geq 4$, then $\chiup_{s}'(G) \leq 2\Delta - 1$; if $G$ is a subcubic graph with girth at least $8$ and $\mad(G) < 2 + \frac{2}{23}$, then $\chiup_{s}'(G) \leq 5$.