On strong edge-colouring of subcubic graphs
On strong edge-colouring of subcubic graphs
复制标题
DOI：
10.1016/j.dam.2013.05.021
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
H. Hocquard;Mickaël Montassier;A. Raspaud;Petru Valicov
中科院分区：
文献类型：
--
作者：
H. Hocquard;Mickaël Montassier;A. Raspaud;Petru Valicov
图G的强边染色是指图G的正常边染色使得每条长度为3的路都使用三种不同的颜色。本文改进了关于次三次图的强边染色的一些结果，证明了每个最大平均度严格小于7.3的次三次图都是强边染色的。5 2，8 3，20 7）可以强烈的边缘着色与六个（分别。七，八，九）颜色。这些上限是最佳的，除了8 3。证明了不含4-圈和5-圈的次立方平面图都可以是九色强边着色图。
A strong edge-colouring of a graph G is a proper edge-colouring such that every path of length 3 uses three different colours. In this paper we improve some previous results on the strong edge-colouring of subcubic graphs by showing that every subcubic graph with maximum average degree strictly less than 7 3 (resp. 5 2, 8 3, 20 7) can be strongly edge-coloured with six (resp. seven, eight, nine) colours. These upper bounds are optimal except the one of 8 3. Also, we prove that every subcubic planar graph without 4-cycles and 5-cycles can be strongly edge-coloured with nine colours.