Header menu link for other important links
X
Acyclic edge colouring of outerplanar graphs
Rahul Muthu, , Subramanian C.R.
Published in Springer Verlag
2007
Volume: 4508 LNCS
   
Pages: 144 - 152
Abstract
An acyclic edge colouring of a graph is a proper edge colouring having no 2-coloured cycle, that is, a colouring in which the union of any two colour classes forms a linear forest. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge colouring using k colours and is usually denoted by a′(G). Determining a′(G) exactly is a very hard problem (both theoretically and algorithmically) and is not determined even for complete graphs. We show that a′(G) ≤ Δ(G) + 1, if G is an outerplanar graph. This bound is tight within an additive factor of 1 from optimality. Our proof is constructive leading to an O(n log Δ) time algorithm. Here, Δ = Δ(G) denotes the maximum degree of the input graph. © Springer-Verlag Berlin Heidelberg 2007.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo