Geodesic
Upper Bounds for the Strong Chromatic Index of Halin Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 5-26

Voir la notice de l'article provenant de la source Library of Science

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].
Keywords: strong edge-coloring, strong chromatic index, Halin graphs 
@article{DMGT_2018_38_1_a0,
     author = {Hu, Ziyu and Lih, Ko-Wei and Liu, Daphne Der-Fen},
     title = {Upper {Bounds} for the {Strong} {Chromatic} {Index} of {Halin} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--26},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/}
}
TY  - JOUR
AU  - Hu, Ziyu
AU  - Lih, Ko-Wei
AU  - Liu, Daphne Der-Fen
TI  - Upper Bounds for the Strong Chromatic Index of Halin Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 5
EP  - 26
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/
LA  - en
ID  - DMGT_2018_38_1_a0
ER  - 
%0 Journal Article
%A Hu, Ziyu
%A Lih, Ko-Wei
%A Liu, Daphne Der-Fen
%T Upper Bounds for the Strong Chromatic Index of Halin Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 5-26
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/
%G en
%F DMGT_2018_38_1_a0
Hu, Ziyu; Lih, Ko-Wei; Liu, Daphne Der-Fen. Upper Bounds for the Strong Chromatic Index of Halin Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 5-26. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a0/