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