- Tytuł:
- Upper Bounds for the Strong Chromatic Index of Halin Graphs
- Autorzy:
-
Hu, Ziyu
Lih, Ko-Wei
Liu, Daphne Der-Fen - Powiązania:
- https://bibliotekanauki.pl/articles/16647759.pdf
- Data publikacji:
- 2018-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
strong edge-coloring
strong chromatic index
Halin graphs - Opis:
- 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].
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 5-26
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł