Upper Bounds for the Strong Chromatic Index of Halin Graphs

• Autorzy: Ziyu Hu , Ko-Wei Lih , Daphne Der-Fen Liu
• Języki publikacji: EN

Abstrakty

EN

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].

Słowa kluczowe

EN

strong edge-coloring; strong chromatic index; Halin graphs

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 38
• Numer: 1
• Strony: 5-26

Daty

wydano

2018-02-01

otrzymano

2015-09-17

poprawiono

2016-08-30

zaakceptowano

2016-08-30

online

2017-12-30

Twórcy

autor

Ziyu Hu

• ,

autor

Ko-Wei Lih

• ,

autor

Daphne Der-Fen Liu

• ,

Identyfikatory

DOI

10.7151/dmgt.2003