Strong edge-colouring of sparse planar graphs

被引：19

作者：

Bensmail, Julien ^{[1
]}

Harutyunyan, Ararat ^{[2
]}

Hocquard, Herve ^{[1
]}

Valicov, Petru ^{[3
]}

机构：

[1] Univ Bordeaux, LaBRI, F-33405 Talence, France

[2] Univ Oxford, Math Inst, Oxford OX1 2JD, England

[3] Ecole Normale Super Lyon, Equipe MC2, LIP, F-69342 Lyon 07, France

来源：

DISCRETE APPLIED MATHEMATICS | 2014年 / 179卷

关键词：

Planar graphs; Girth; Proper edge-colouring; Strong edge-colouring; STRONG CHROMATIC INDEX; MAXIMUM DEGREE-7;

D O I：

10.1016/j.dam.2014.07.006

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 4 has a strong ;edge-colouring with at most 4 Delta + 4 colours. We show that 3 Delta + 1 colours suffice if the graph has girth 6, and 4 Delta colours suffice if Delta >= 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. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：229 / 234

页数：6

共 14 条

[1] THE STRONG CHROMATIC INDEX OF A CUBIC GRAPH IS AT MOST 10 [J].