List star edge coloring of generalized Halin graphs

Abstract

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\Delta }{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\Delta }{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 $\Delta (T)\ge 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|\ne 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 $\theta (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 $\Delta \ge 13$, then the list star chromatic index is at most $\lfloor \frac{3\Delta }{2}\rfloor$. Moreover, the upper bound for the list star chromatic index is sharp.