The star chromatic index of a graph $ G $, denoted by $ \chi'_{st}(G) $, is the minimum number of colors needed to properly color the edges of $ G $ such that no path or cycle of length four is bi-colored. Casselgren et al. and Hou et al. independently proved that the star chromatic index of a cubic Halin graph, except in the case of a special graph, is at most $ 6 $. It remains an open problem to determine which of such graphs have star chromatic index $ 5 $. In this paper, we show that if $ G\ne N_{e_2} $ is a cubic Halin graph whose tree is a caterpillar or a complete tree, then $ \chi'_{st}(G) = 5 $.
Citation: Xingxing Hu, Yunfang Tang. The star edge coloring of cubic Halin graphs with star chromatic index $ 5 $[J]. AIMS Mathematics, 2026, 11(1): 3132-3141. doi: 10.3934/math.2026124
The star chromatic index of a graph $ G $, denoted by $ \chi'_{st}(G) $, is the minimum number of colors needed to properly color the edges of $ G $ such that no path or cycle of length four is bi-colored. Casselgren et al. and Hou et al. independently proved that the star chromatic index of a cubic Halin graph, except in the case of a special graph, is at most $ 6 $. It remains an open problem to determine which of such graphs have star chromatic index $ 5 $. In this paper, we show that if $ G\ne N_{e_2} $ is a cubic Halin graph whose tree is a caterpillar or a complete tree, then $ \chi'_{st}(G) = 5 $.
| [1] |
X. Liu, K. Deng, An upper bound on the star chromatic index of graphs with $\Delta\ge 7$, J. Lanzhou Univ., 44 (2008), 98–99. https://doi.org/10.13885/j.issn.0455-2059.2008.02.003 doi: 10.13885/j.issn.0455-2059.2008.02.003
|
| [2] |
Z. Dvořák, B. Mohar, R. Šámal, Star chromatic index, J. Graph Theor., 72 (2013), 313–326. https://doi.org/10.1002/jgt.21644 doi: 10.1002/jgt.21644
|
| [3] |
H. Lei, Y. Shi, Z. X. Song, Star chromatic index of subcubic multigraphs, J. Graph Theor., 88 (2018), 566–576. https://doi.org/10.1002/jgt.22230 doi: 10.1002/jgt.22230
|
| [4] |
L. Bezegová, B. Lužar, M. Mockovčiaková, R. Soták, R. Škrekovski, Star edge coloring of some classes of graphs, J. Graph Theor., 81 (2016), 73–82. https://doi.org/10.1002/jgt.21862 doi: 10.1002/jgt.21862
|
| [5] |
H. Lei, Y. Shi, Z. X. Song, T. Wang, Star 5-edge-colorings of subcubic multigraphs, Discrete Math., 341 (2018), 950–956. https://doi.org/10.1016/j.disc.2017.12.008 doi: 10.1016/j.disc.2017.12.008
|
| [6] |
H. Lei, Y. Shi, A survey on star edge colorings of graphs, Adv. Math., 50 (2021), 77–93. https://doi.org/10.11845/sxjz.2020006a doi: 10.11845/sxjz.2020006a
|
| [7] |
C. J. Casselgren, J. Granholm, A. Raspaud, On star edge colorings of bipartite and subcubic graphs, Discrete Appl. Math., 298 (2021), 21–33. https://doi.org/10.1016/j.dam.2021.03.007 doi: 10.1016/j.dam.2021.03.007
|
| [8] | X. Hou, L. Li, T. Wang, Star edge coloring of some special graphs, arXiv Preprint, 2020. https://doi.org/10.48550/arXiv.2010.14349 |
| [9] |
K. W. Lih, D. Liu, On the strong chromatic index of cubic Halin graphs, Appl. Math. Lett., 25 (2012), 898–901. https://doi.org/10.1016/j.aml.2011.10.046 doi: 10.1016/j.aml.2011.10.046
|
| [10] |
W. Yang, B. Wu, Proof of a conjecture on the strong chromatic index of Halin graphs, Discrete Appl. Math., 302 (2021), 92–102. https://doi.org/10.1016/j.dam.2021.06.016 doi: 10.1016/j.dam.2021.06.016
|
| [11] |
W. C. Shiu, W. K. Tam, The strong chromatic index of complete cubic Halin graphs, Appl. Math. Lett., 22 (2009), 754–758. https://doi.org/10.1016/j.aml.2008.08.019 doi: 10.1016/j.aml.2008.08.019
|
| [12] | W. C. Shiu, P. C. B. Lam, W. K. Tam, On strong chromatic index of Halin graphs, J. Combin. Math. Combin. Comput., 57 (2006), 211–222. Available from: https://www.researchgate.net/publication/238636258. |
| [13] |
G. J. Chang, D. Liu, Strong edge-coloring for cubic Halin graphs, Discrete Math., 312 (2012), 1468–1475. https://doi.org/10.1016/j.disc.2012.01.014 doi: 10.1016/j.disc.2012.01.014
|
Figures(10)
Xingxing Hu, Yunfang Tang. The star edge coloring of cubic Halin graphs with star chromatic index $ 5 $[J]. AIMS Mathematics, 2026, 11(1): 3132-3141. doi: 10.3934/math.2026124
DownLoad: