Strong Edge-Coloring Of Planar Graphs

Wen-Yao Song, and Lian-Ying Miao. "Strong Edge-Coloring Of Planar Graphs." Discussiones Mathematicae Graph Theory 37.4 (2017): 845-857. <http://eudml.org/doc/288320>.

@article{Wen2017,
abstract = {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.},
author = {Wen-Yao Song, Lian-Ying Miao},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {strong edge-coloring; strong chromatic index; planar graph; dis- charging method.},
language = {eng},
number = {4},
pages = {845-857},
title = {Strong Edge-Coloring Of Planar Graphs},
url = {http://eudml.org/doc/288320},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Wen-Yao Song
AU - Lian-Ying Miao
TI - Strong Edge-Coloring Of Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 4
SP - 845
EP - 857
AB - 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.
LA - eng
KW - strong edge-coloring; strong chromatic index; planar graph; dis- charging method.
UR - http://eudml.org/doc/288320
ER -