Acyclic edge colouring of planar graphs without short cycles
Acyclic edge colouring of planar graphs without short cycles
复制标题
DOI：
10.1016/j.disc.2009.06.007
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
M. Borowiecki;A. Fiedorowicz
中科院分区：
文献类型：
--
作者：
M. Borowiecki;A. Fiedorowicz
设G=（V，E）是任意有限图.一个映射C：E→[k]称为G的无圈边k-染色，如果G中任意两条相邻边有不同的颜色，且G中不存在双色圈.换句话说，对于每一对不同的颜色i和j，G中所有具有颜色i或j的边所诱导的子图是非循环的。使G具有无圈边k-染色的最小颜色数k称为G的无圈色指数，记为χa′（G）。2001年，Alon et al.证明了对任意图G，有χa′（G）≤Δ（G）+2，其中Δ（G）表示G的最大度.本文对围长至少为5的平面图和不含长为4，6，8，9的圈的平面图证明了这个猜想。我们还证明了当G是围长至少为6的平面图时，χa′（G）≤Δ（G）+1.此外，我们还找到了不含圈长为4的平面图的无圈色指数的一个上界。也就是说，我们证明了：如果G是这样的图，则χa′（G）≤Δ（G）+15。
Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges which have colour i or j, is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G, denoted by χa′(G). In 2001, Alon et al. conjectured that for any graph G it holds that χa′(G)≤Δ(G)+2; here Δ(G) stands for the maximum degree of G. In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that χa′(G)≤Δ(G)+1 if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then χa′(G)≤Δ(G)+15.