On the precise value of the strong chromatic-index of a planar graph with a large girth

Abstract

A strong $k$-edge-coloring of a graph $G$ is a mapping from $E(G)$ to $\{1,2,\dots ,k\}$ such that every pair of distinct edges at distance at most two receive different colors. The strong chromatic index ${\chi }_s^{\prime }(G)$ of a graph $G$ is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. Denote $\sigma (G)={\max }_{xy\in E(G)}\{\mathrm{deg}(x)+\mathrm{deg}(y)-1\}$. It is easy to see that $\sigma (G)\le {\chi }_s^{\prime }(G)$ for any graph $G$, and the equality holds when $G$ is a tree. For a planar graph $G$ of maximum degree $\Delta$, it was proved that ${\chi }_s^{\prime }(G)\le 4\Delta +4$ by using the Four Color Theorem. The upper bound was then reduced to $4\Delta$, $3\Delta +5$, $3\Delta +1$, $3\Delta$, $2\Delta -1$ under different conditions for $\Delta$ and the girth. In this paper, we prove that if the girth of a planar graph $G$ is large enough and $\sigma (G)\ge \Delta (G)+2$, then the strong chromatic index of $G$ is precisely $\sigma (G)$. This result reflects the intuition that a planar graph with a large girth locally looks like a tree.

16 pages, 2 figures