Article ID Journal Published Year Pages File Type
4649394 Discrete Mathematics 2010 11 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be any finite graph. A mapping C:E→[k]C:E→[k] is called an acyclic edge  kk-colouring   of GG, if any two adjacent edges have different colours and there are no bichromatic cycles in GG. In other words, for every pair of distinct colours ii and jj, the subgraph induced in GG by all the edges which have colour ii or jj, is acyclic. The smallest number kk of colours, such that GG has an acyclic edge kk-colouring is called the acyclic chromatic index   of GG, denoted by χa′(G).In 2001, Alon et al. conjectured that for any graph GG it holds that χa′(G)≤Δ(G)+2; here Δ(G)Δ(G) stands for the maximum degree of GG.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,84,6,8 and 9. We also show that χa′(G)≤Δ(G)+1 if GG 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 GG is such a graph, then χa′(G)≤Δ(G)+15.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,