Strong Edge-Coloring Of Planar Graphs

• Autorzy: Wen-Yao Song , Lian-Ying Miao
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

strong edge-coloring; strong chromatic index; planar graph; dis- charging method.

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 4
• Strony: 845-857

Daty

wydano

2017-11-27

otrzymano

2015-08-16

poprawiono

2016-06-28

zaakceptowano

2016-06-30

online

2017-09-02

Twórcy

autor

Wen-Yao Song

• 221116, P.R.

autor

Lian-Ying Miao

• 221116, P.R.

Identyfikatory

DOI

10.7151/dmgt.1951