Authors:
D. D.-F. Liu, Z. Hu, K.-W. Lih
Title:
Upper bounds for the strong chromatic index of Halin graphs
Source:
Discussiones Mathematicae Graph Theory
Received 17.09.2015, Revised 30.08.2016, Accepted 30.08.2016, doi: 10.7151/dmgt.2003

Abstract:
The strong chromatic index of a graph G, denoted by \sk(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 \sk(G) ≤ 2Δ + 1 when Δ ≥ 4. In addition, we show that if Δ = 4 and G is not a wheel, then \sk(G)≤ \sk(T) +2. A similar result for Δ=3 was established by Lih and Liu \cite{LL2011}.
Keywords:
strong edge-coloring, strong chromatic index, Halin graphs

Links:
PDF