کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649394 | 1342452 | 2010 | 11 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 310, Issue 9, 6 May 2010, Pages 1445–1455