

























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 \cite{MR2933839}, and Bezegov{á} \etal \cite{MR3431294} independently proved that the star chromatic index of a tree is at most $\lfloor \frac{3Δ}{2} \rfloor$, and the bound is sharp. Han \etal \cite{MR3924408} strengthened the result to list version of star chromatic index, and proved that $\lfloor \frac{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) \geq 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 \cup C$ is a generalized Halin graph with $|C| \neq 5$, then its list star chromatic index is at most \[ \max\left\{\left\lfloor\frac{θ(T) + Δ(T)}{2}\right\rfloor, 2 \left\lfloor\frac{Δ(T)}{2}\right\rfloor + 7\right\}, \] where $θ(T) = \max_{xy \in E(T)}\{d_{T}(x) + d_{T}(y)\}$. As a consequence, if $H$ is a (generalized) Halin graph with maximum degree $Δ\geq 13$, then the list star chromatic index is at most $\lfloor \frac{3Δ}{2} \rfloor$. Moreover, the upper bound for the list star chromatic index is sharp.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。