Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418699 | Discrete Applied Mathematics | 2014 | 6 Pages |
Abstract
A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree ΔΔ has a strong edge-colouring with at most 4Δ+44Δ+4 colours. We show that 3Δ+13Δ+1 colours suffice if the graph has girth 6, and 4Δ4Δ colours suffice if Δ≥7Δ≥7 or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Julien Bensmail, Ararat Harutyunyan, Hervé Hocquard, Petru Valicov,