Article ID Journal Published Year Pages File Type
6423393 Discrete Mathematics 2014 9 Pages PDF
Abstract

A strong edge-coloring of a graph is a proper edge-coloring where the edges at distance at most 2 receive distinct colors. It is known that every planar graph G has a strong edge-coloring with at most 4Δ(G)+4 colors. We show that 3Δ(G)+5 colors suffice if G has girth 6, and 3Δ(G) colors suffice if its girth is at least 7. Moreover, we show that cubic planar graphs with girth at least 6 can be strongly edge-colored with at most nine colors.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,