The tight bound for the strong chromatic indices of claw-free subcubic graphs

Abstract

Let $G$ be a graph and $k$ a positive integer. A strong $k$-edge-coloring of $G$ is a mapping $\varphi :E(G)\to \{1,2,\dots ,k\}$ such that for any two edges $e$ and $e^{\prime }$ that are either adjacent to each other or adjacent to a common edge, $\varphi (e)\ne \varphi (e^{\prime })$. The strong chromatic index of $G$, denoted as ${\chi }_s^{\prime }(G)$, is the minimum integer $k$ such that $G$ has a strong $k$-edge-coloring. Lv, Li and Zhang [Graphs and Combinatorics 38 (3) (2022) 63] proved that if $G$ is a claw-free subcubic graph other than the triangular prism then ${\chi }_s^{\prime }(G)\le 8$. In addition, they asked if the upper bound $8$ can be improved to $7$. In this paper, we answer this question in the affirmative. Our proof implies a linear-time algorithm for finding strong $7$-edge-colorings of such graphs. We also construct infinitely many claw-free subcubic graphs with their strong chromatic indices attaining the bound $7$.

18 pages, 16 figures