Strong edge-coloring of planar graphs
Author(s) -
Lianying Miao,
Wenyao Song
Publication year - 2017
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1951
Subject(s) - edge coloring , combinatorics , mathematics , planar graph , graph , graph coloring , brooks' theorem , discrete mathematics , graph power , line graph
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom