Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423393 | Discrete Mathematics | 2014 | 9 Pages |
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
Dávid Hudák, Borut Lužar, Roman Soták, Riste Å krekovski,