2021/04/13 by Zhengke Miao, Yimin Song, Miao, Zhengke +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2104.05958
openalex publication_date 2021/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A star k-edge coloring is a proper edge coloring such that there are no bichromatic paths or cycles of length four. The smallest integer k such that G admits a star k-edge coloring is the star chromatic index of G. Deng \etal \citeMR2933839, and Bezegová \etal \citeMR3431294 independently proved that the star chromatic index of a tree is at most \lfloor (3Δ)/(2) \rfloor, and the bound is sharp. Han \etal \citeMR3924408 strengthened the result to list version of star chromatic index, and proved that \lfloor (3Δ)/(2) \rfloor is also the sharp upper bound for the list star chromatic index of trees. A generalized Halin graph is a plane graph that consists of a plane embedding of a tree T with Δ(T) ≥ 3, and a cycle C connecting all the leaves of the tree such that C is the boundary of the exterior face. In this paper, we prove that if H := T ∪ C is a generalized Halin graph with |C| ≠ 5, then its list star chromatic index is at most max\\lfloor(θ(T) + Δ(T))/(2)\rfloor, 2 \lfloor(Δ(T))/(2)\rfloor + 7\, where θ(T) = maxxy ∈ E(T)\dT(x) + dT(y)\. As a consequence, if H is a (generalized) Halin graph with maximum degree Δ≥ 13, then the list star chromatic index is at most \lfloor (3Δ)/(2) \rfloor. Moreover, the upper bound for the list star chromatic index is sharp.