The strong chromatic index of a graph G, denoted by χ′s(G), is the minimum number of vertex induced matchings needed to partition the edge set of G. Let T be a tree without vertices of degree 2 and have at least one vertex of degree greater than 2. We construct a Halin graph G by drawing T on the plane and then drawing a cycle C connecting all its leaves in such a way that C forms the boundary of the unbounded face. We call T the characteristic tree of G. Let G denote a Halin graph with maximum degree Δ and characteristic tree T. We prove that χ′s(G) ⩽ 2Δ + 1 when Δ ⩾ 4. In addition, we show that if Δ = 4 and G is not a wheel, then χ′s(G) ⩽ χ′s(T) + 2. A similar result for Δ = 3 was established by Lih and Liu [21].
@article{bwmeta1.element.doi-10_7151_dmgt_2003,
author = {Ziyu Hu and Ko-Wei Lih and Daphne Der-Fen Liu},
title = {Upper Bounds for the Strong Chromatic Index of Halin Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {38},
year = {2018},
pages = {5-26},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_2003}
}
Ziyu Hu; Ko-Wei Lih; Daphne Der-Fen Liu. Upper Bounds for the Strong Chromatic Index of Halin Graphs. Discussiones Mathematicae Graph Theory, Tome 38 (2018) pp. 5-26. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_2003/