Upper Bounds for the Strong Chromatic Index of Halin Graphs

Ziyu Hu, Ko-Wei Lih, and Daphne Der-Fen Liu. "Upper Bounds for the Strong Chromatic Index of Halin Graphs." Discussiones Mathematicae Graph Theory 38.1 (2018): 5-26. <http://eudml.org/doc/288408>.

@article{ZiyuHu2018,
abstract = {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].},
author = {Ziyu Hu, Ko-Wei Lih, Daphne Der-Fen Liu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {strong edge-coloring; strong chromatic index; Halin graphs},
language = {eng},
number = {1},
pages = {5-26},
title = {Upper Bounds for the Strong Chromatic Index of Halin Graphs},
url = {http://eudml.org/doc/288408},
volume = {38},
year = {2018},
}

TY - JOUR
AU - Ziyu Hu
AU - Ko-Wei Lih
AU - Daphne Der-Fen Liu
TI - Upper Bounds for the Strong Chromatic Index of Halin Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2018
VL - 38
IS - 1
SP - 5
EP - 26
AB - 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].
LA - eng
KW - strong edge-coloring; strong chromatic index; Halin graphs
UR - http://eudml.org/doc/288408
ER -