论文标题
紧密结合了无爪子皮图的强色指数
The tight bound for the strong chromatic indices of claw-free subcubic graphs
论文作者
论文摘要
让$ g $为图，$ k $一个正整数。 $ g $的强$ K $ - 颜色是映射$ ϕ：e（g）\ to \ {1,2，\ dots，k \} $，以至于对于任何两个边缘$ e $和$ e'$，它们彼此相邻或与common Edge相邻或相邻的共同边缘，$ ϕ（e）\ neq（e）\ neq（e）（e）（e）$。 $ g $的强色指数为$χ'_{s}（g）$，是最小整数$ k $，因此$ g $具有强大的$ k $ - edge-gede-coloring。 LV，Li和Zhang [图和组合学38（3）（2022）63]证明，如果$ g $是三角形棱镜以外的无爪子皮图，则$χ_s'（g）\ le 8 $。此外，他们询问上限$ 8 $是否可以提高到$ 7 $。在本文中，我们以肯定的方式回答了这个问题。我们的证明意味着一种线性时间算法，用于找到此类图的强劲$ 7 $ - 边缘。我们还无限地构建了许多无爪的亚立方图，其强大的色度指数达到了$ 7 $。
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$.
