Upper Bounds for the Strong Chromatic Index of Halin Graphs
| Autor: | Ko-Wei Lih, Daphne Der-Fen Liu, Ziyu Hu |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
halin graphs
Applied Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences Treewidth Combinatorics Edge coloring 010201 computation theory & mathematics 05c15 QA1-939 Discrete Mathematics and Combinatorics 0101 mathematics Halin graph strong chromatic index Mathematics strong edge-coloring |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 38, Iss 1, Pp 5-26 (2018) |
| ISSN: | 2083-5892 |
| 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: | OpenAIRE |
| Externí odkaz: |
|