2022/07/21 by Yuquan Lin, Lin, Yuquan, Wensong Lin +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2207.10264
openalex publication_date 2022/07/21 · openalex created_date 2022/07/23 · openalex updated_date 2026/07/28
Let G be a graph and k a positive integer. A strong k-edge-coloring of G is a mapping ϕ: E(G)→ \1,2,…,k\ such that for any two edges e and e' that are either adjacent to each other or adjacent to a common edge, ϕ(e)≠ ϕ(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)≤ 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.