Strong edge-coloring of planar graphs

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 i...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2014-06, Vol.324, p.41-49
Main Authors: Hudak, David, Luzar, Borut, Sotak, Roman, Skrekovski, Riste
Format: Article
Language:English
Subjects:
Discharging method
Graphs
Mathematical analysis
Planar graph
Strong chromatic index
Strong edge-coloring
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2014.02.002