List star edge coloring of generalized Halin graphs
List star edge coloring of generalized Halin graphs
复制标题
DOI：
10.1016/j.disc.2022.113204
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Z. Miao;Yimin Song;Tao-Ming Wang;Xiaowei Yu
中科院分区：
文献类型：
--
作者：
Z. Miao;Yimin Song;Tao-Ming Wang;Xiaowei Yu
一个星星k-边染色是一个正常的边染色，使得不存在长度为4的双色路或圈。使G允许星星k-边染色的最小整数k是G的星星色指数。deng等人[5]，and Bezová et al. [1]独立地证明了树的星色指数至多为<$3 Δ 2 <$$>，且界是尖锐的. han等人[8]将该结果推广到树的列表型星星色指数，并证明了树的列表型星星色指数的上界也是λ 3 Δ 2 λ。广义Halin图是一个平面图，它由一个Δ（T）≥ 3的树T的平面嵌入和一个连接树的所有叶子的圈C组成，使得C是外表面的边界。本文证明了：如果H_T_C是广义Halin图，|C|星星的表色指数至多为max {，2 + 7}，其中θ（T）= max xy ∈ E（T）{dT（x）+dT（y）}.因此，如果H是最大度Δ ≥ 13的（广义）Halin图，则列表星星色指数至多为Δ 3 Δ 2 λ.此外，列表星星色指数的上界是尖锐的。
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 et al.[5], and Bezegová et al.[1] independently proved that the star chromatic index of a tree is at most⌊ 3 Δ 2⌋, and the bound is sharp. Han et al.[8] strengthened the result to list version of star chromatic index, and proved that⌊ 3 Δ 2⌋ 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{⌊ θ (T)+ Δ (T) 2⌋, 2⌊ Δ (T) 2⌋+ 7}, where θ (T)= max x y∈ E (T){d T (x)+ d T (y)}. As a consequence, if H is a (generalized) Halin graph with maximum degree Δ≥ 13, then the list star chromatic index is at most⌊ 3 Δ 2⌋. Moreover, the upper bound for the list star chromatic index is sharp.