Strong edge-colouring of sparse planar graphs

被引：18
作者：
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
    ANDERSEN, LD
    [J]. DISCRETE MATHEMATICS, 1992, 108 (1-3) : 231 - 252
  • [2] PRECISE UPPER BOUND FOR THE STRONG EDGE CHROMATIC NUMBER OF SPARSE PLANAR GRAPHS
    Borodin, Oleg V.
    Ivanova, Anna O.
    [J]. DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (04) : 759 - 770
  • [3] Chang G.J., 2013, CRM SERIES, P265
  • [4] PROBLEMS AND RESULTS IN COMBINATORIAL ANALYSIS AND GRAPH-THEORY
    ERDOS, P
    [J]. DISCRETE MATHEMATICS, 1988, 72 (1-3) : 81 - 92
  • [5] Erdos P., 1989, Irregularities of partitions, Algorithms and Combinatorics: Study and Research Texts, V8, P162
  • [6] FAUDREE RJ, 1990, ARS COMBINATORIA, V29B, P205
  • [7] On strong edge-colouring of subcubic graphs
    Hocquard, Herve
    Montassier, Mickael
    Raspaud, Andre
    Valicov, Petru
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) : 2467 - 2479
  • [8] INDUCED MATCHINGS IN CUBIC GRAPHS
    HORAK, P
    QING, H
    TROTTER, WT
    [J]. JOURNAL OF GRAPH THEORY, 1993, 17 (02) : 151 - 160
  • [9] Strong edge-coloring of planar graphs
    Hudak, David
    Luzar, Borut
    Sotak, Roman
    Skrekovski, Riste
    [J]. DISCRETE MATHEMATICS, 2014, 324 : 41 - 49
  • [10] Edge Coloring of embedded graphs with large girth
    Li, XC
    Luo, R
    [J]. GRAPHS AND COMBINATORICS, 2003, 19 (03) : 393 - 401
12