






















Let $G$ be a graph and $k$ a positive integer. A strong $k$-edge-coloring of $G$ is a mapping $φ: E(G)\to \{1,2,\dots,k\}$ such that for any two edges $e$ and $e'$ that are either adjacent to each other or adjacent to a common edge, $φ(e)\neq φ(e')$. The strong chromatic index of $G$, denoted as $χ'_{s}(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 $χ_s'(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$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。