# Upper Bounds for the Strong Chromatic Index of Halin Graphs

Ziyu Hu; Ko-Wei Lih; Daphne Der-Fen Liu

Discussiones Mathematicae Graph Theory (2018)

- Volume: 38, Issue: 1, page 5-26
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topZiyu 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.