Star edge-coloring of Halin graphs.
2021
The star chromatic index $\chi'_{st}(G)$ of a graph $G$ is the smallest
integer $k$ for which $G$ has a proper $k$-edge coloring without bichromatic
paths or cycles of length four. In 2016, Bezegov\'{a}, Lu\v{z}ar,
Mockov\v{c}iakov\'{a}, Sot\'{a}k, and \v{S}krekovski [Star edge coloring of
some classes of graphs, J. Graph Theory, 81 (1): 73-82, 2016] conjectured every
outerplanar graph with maximum degree at least 4 admits a star
$\left(\left\lfloor\frac{3\Delta}{2}\right\rfloor+1\right)$-edge coloring. In
this paper, we support this conjecture by proving that if $H$ is a Halin graph
with maximum degree $\Delta\ge 14$, then $\chi'_{st}(H)\leq
\lfloor\frac{3}{2}\Delta\rfloor$. This bound is tight.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
0
Citations
NaN
KQI