For a graph $ G $, a semistrong matching is a matching $ M $ such that every edge in $ M $ contains at least one endpoint of degree one in the induced subgraph $ G[V(M)] $. The semistrong chromatic index $ \chi_{s s}^{\prime}(G) $ denotes the minimum number of colors required for a proper edge-coloring where each color class induces a semistrong matching. We study this parameter for Halin graphs, which are planar graphs formed by connecting all leaves of a tree $ T $ (with no degree-two vertices) via an outer cycle $ C $. Our main result establishes that for any Halin graph $ G = T\cup C $ with maximum degree $ \Delta(G) $, the semistrong chromatic index satisfies $ \chi_{s s}^{\prime}(G) \leq \Delta(G)+4 $, with equality attained by the wheel graphs $ W_4 $ and $ W_7 $.
Citation: Jianxin Luo, Jiangxu Kong. An upper bound for the semistrong chromatic index of Halin graphs[J]. AIMS Mathematics, 2025, 10(7): 15811-15820. doi: 10.3934/math.2025708
For a graph $ G $, a semistrong matching is a matching $ M $ such that every edge in $ M $ contains at least one endpoint of degree one in the induced subgraph $ G[V(M)] $. The semistrong chromatic index $ \chi_{s s}^{\prime}(G) $ denotes the minimum number of colors required for a proper edge-coloring where each color class induces a semistrong matching. We study this parameter for Halin graphs, which are planar graphs formed by connecting all leaves of a tree $ T $ (with no degree-two vertices) via an outer cycle $ C $. Our main result establishes that for any Halin graph $ G = T\cup C $ with maximum degree $ \Delta(G) $, the semistrong chromatic index satisfies $ \chi_{s s}^{\prime}(G) \leq \Delta(G)+4 $, with equality attained by the wheel graphs $ W_4 $ and $ W_7 $.
| [1] |
G. J. Chang, D. D. F. 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
|
| [2] |
K. Deng, G. Yu, X. Zhou, Recent progress on strong edge-coloring of graphs, Discrete Math. Algor. Appl., 11 (2019), 1950062. https://doi.org/10.1142/S1793830919500629 doi: 10.1142/S1793830919500629
|
| [3] | P. Erdős, J. Nešetřil, Problem, In: Irregularities of partitions, Berlin: Springer, 1989,162–163. |
| [4] | R. J. Faudree, R. H. Schelp, A. Gyárfás, Z. Tuza, The strong chromatic index of graphs, Ars Combin., 29 (1990), 205–211. |
| [5] |
A. Gyárfás, A. Hubenko, Semistrong edge-coloring of graphs, J. Graph Theory, 49 (2005), 39–47. https://doi.org/10.1002/jgt.20061 doi: 10.1002/jgt.20061
|
| [6] |
Z. Hu, K. W. Lih, D. D. F. Liu, Upper bounds for the strong chromatic index of Halin graphs, Discuss. Math. Graph Theory, 38 (2018), 5–26. http://doi.org/10.7151/dmgt.2003 doi: 10.7151/dmgt.2003
|
| [7] | Y. Lin, W. Lin, Proving a conjecture on the upper bound of semistrong chromatic indices of graphs, preprint paper, 2023. https://doi.org/10.48550/arXiv.2310.12552 |
| [8] | Y. Lin, W. Lin, Semistrong edge-colorings of planar graphs, preprint paper, 2024. https://doi.org/10.48550/arXiv.2412.19230 |
| [9] |
H. H. Lai, K. W. Lih, P. Y. Tsai, The strong chromatic index of Halin graphs, Discrete Math., 312 (2012), 1536–1541. https://doi.org/10.1016/j.disc.2011.09.016 doi: 10.1016/j.disc.2011.09.016
|
| [10] |
B. Lužar, M. Mockovčiaková, R. Soták, Revisiting semistrong edge-coloring of graphs, J. Graph Theory, 105 (2024), 612–632. https://doi.org/10.1002/jgt.23059 doi: 10.1002/jgt.23059
|
| [11] |
K. W. Lih, D. D. F. 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
|
| [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. |
| [13] |
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
|
| [14] |
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
|
Figures(5)
Jianxin Luo, Jiangxu Kong. An upper bound for the semistrong chromatic index of Halin graphs[J]. AIMS Mathematics, 2025, 10(7): 15811-15820. doi: 10.3934/math.2025708
DownLoad: