- Tytuł:
- Strong Edge-Coloring Of Planar Graphs
- Autorzy:
-
Song, Wen-Yao
Miao, Lian-Ying - Powiązania:
- https://bibliotekanauki.pl/articles/31341618.pdf
- Data publikacji:
- 2017-11-27
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
strong edge-coloring
strong chromatic index
planar graph
dis- charging method - Opis:
- A strong edge-coloring of a graph is a proper edge-coloring where each color class induces a matching. We denote by $ \chi_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 \Delta (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 \ge 5$, then $ \chi_s^' (G) \le 4 \Delta (G) − 2 $ when $ \Delta (G) \ge 6 $ and $ \chi_s^' (G) \le 19 $ when $ \Delta (G) = 5 $, where $g$ is the girth of $G$.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 845-857
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł