Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: strong edge-coloring

Sortuj według:

Ogranicz wyniki do:

Strong Edge-Coloring Of Planar Graphs

100%

Song W.-Y., Miao L.-Y.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 4

845-857

A strong edge-coloring of a graph is a proper edge-coloring where each color class induces a matching. We denote by 𝜒's(G) the strong chromatic index of G which is the smallest integer k such that G can be strongly edge-colored with k colors. It is known that every planar graph G has a strong edge-coloring with at most 4 Δ(G) + 4 colors [R.J. Faudree, A. Gyárfás, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211]. In this paper, we show that if G is a planar graph with g ≥ 5, then 𝜒's(G) ≤ 4(G) − 2 when Δ(G) ≥ 6 and 𝜒's(G) ≤ 19 when Δ(G) = 5, where g is the girth of G.

Upper Bounds for the Strong Chromatic Index of Halin Graphs

100%

Hu Z., Lih K.-W., Liu D. D.-F.

Discussiones Mathematicae Graph Theory

2017

tom 38

nr 1

5-26

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].

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Hu Z.

1 Lih K.-W.

1 Liu D. D.-F.

1 Miao L.-Y.

1 Song W.-Y.

1 2018

1 2017

Wyniki wyszukiwania

Strong Edge-Coloring Of Planar Graphs

Upper Bounds for the Strong Chromatic Index of Halin Graphs