language-icon Old Web
English
Sign In

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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    9
    References
    0
    Citations
    NaN
    KQI
    []