Header menu link for other important links
X
About acyclic edge colourings of planar graphs
Anna Fiedorowicz, Mariusz Hałuszczak,
Published in Elsevier BV
2008
Volume: 108
   
Issue: 6
Pages: 412 - 417
Abstract
Let G = (V, E) be any finite simple graph. A mapping C : E → [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 by all the edges which have either 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 $\chi$a′ (G). In 1991, Alon et al. [N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991) 277-288] proved that $\chi$a′ (G) ≤ 64 $\Delta$ (G) for any graph G of maximum degree $\Delta$ (G). This bound was later improved to 16 $\Delta$ (G) by Molloy and Reed in [M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524-529]. In this paper we prove that $\chi$a′ (G) ≤ $\Delta$ (G) + 6 for a planar graph G without cycles of length three and that the same holds if G has an edge-partition into two forests. We also show that $\chi$a′ (G) ≤ 2 $\Delta$ (G) + 29 if G is planar. {\textcopyright} 2008 Elsevier B.V. All rights reserved.
About the journal
JournalData powered by TypesetInformation Processing Letters
PublisherData powered by TypesetElsevier BV
ISSN00200190
Open AccessNo