Article ID Journal Published Year Pages File Type
418699 Discrete Applied Mathematics 2014 6 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,