کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428657 | 686857 | 2011 | 4 صفحه PDF | دانلود رایگان |

Let G be any finite graph. A mapping c:E(G)→{1,…,k}c:E(G)→{1,…,k} is called an acyclic edge k-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 that 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 and is denoted by χa′(G).Determining the acyclic chromatic index of a graph is a hard problem, both from theoretical and algorithmical point of view. In 1991, Alon et al. proved that χa′(G)⩽64Δ(G) for any graph G of maximum degree Δ(G)Δ(G). This bound was later improved to 16Δ(G)16Δ(G) by Molloy and Reed. In general, the problem of computing the acyclic chromatic index of a graph is NP-complete. Only a few algorithms for finding acyclic edge colourings have been known by now. Moreover, these algorithms work only for graphs from particular classes.In our paper, we prove that χa′(G)⩽(t−1)Δ(G)+p for every graph G which satisfies the condition that |E(G′)|⩽t|V(G′)|−1|E(G′)|⩽t|V(G′)|−1 for each subgraph G′⊆GG′⊆G, where t⩾2t⩾2 is a given integer, the constant p=2t3−3t+2p=2t3−3t+2. Based on that result, we obtain a polynomial algorithm which computes such a colouring. The class of graphs covered by our theorem is quite rich, for example, it contains all t-degenerate graphs.
Research highlights
► We consider graphs with the number of edges linearly bounded by the number of vertices.
► We obtain an upper bound for the acyclic edge chromatic number of such graphs.
► We present a polynomial algorithm for an acyclic edge colouring.
► We give an upper bound for the acyclic edge chromatic number of degenerate graphs.
Journal: Information Processing Letters - Volume 111, Issue 6, 15 February 2011, Pages 287–290