| Autor: |
Hu Ziyu, Lih Ko-Wei, Liu Daphne Der-Fen |
| Jazyk: |
angličtina |
| Rok vydání: |
2018 |
| Předmět: |
|
| Zdroj: |
Discussiones Mathematicae Graph Theory, Vol 38, Iss 1, Pp 5-26 (2018) |
| Druh dokumentu: |
article |
| ISSN: |
2083-5892 |
| DOI: |
10.7151/dmgt.2003 |
| Popis: |
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]. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
