Article ID Journal Published Year Pages File Type
420145 Discrete Applied Mathematics 2012 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. 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 χ′(G)χ′(G).In 1978, Fiamčík conjectured that for any graph GG it holds χ′(G)≤Δ(G)+2χ′(G)≤Δ(G)+2, where Δ(G)Δ(G) stands for the maximum degree of GG. This conjecture has been verified by now only for some special classes of graphs. In 2010, Borowiecki and Fiedorowicz confirmed it for planar graph with girth at least 5. In this paper, we improve the above result, by proving that if GG is a plane graph such that for each pair i,j∈{3,4}i,j∈{3,4}, no ii-face and a jj-face share a common vertex in GG, then χ′(G)≤Δ(G)+2χ′(G)≤Δ(G)+2.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,