Acyclic edge colourings of graphs with the number of edges linearly bounded by the number of vertices

摘要

Let C be any finite graph. A mapping 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 X'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 X'a(G)≤ 64A(G) for any graph G of maximum degree A(G). This bound was later improved to 16A(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 X'a(G)≤(t - 1)△(G) + p for every graph G which satisfies the condition that |£(G')| ≤ t|V(G')| - 1 for each subgraph G' is contained in G, where t ≥ 2 is a given integer, the constant p = 2t~3 - 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.