Loading…

Analysis of a heuristic for acyclic edge colouring

An acyclic edge colouring of a graph is a proper edge colouring in which the union of any two colour classes does not contain a cycle, that is, forms a forest. It is known that there exists such a colouring using at most 16 Δ ( G ) colours where Δ ( G ) denotes the maximum degree of a graph G. Howev...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2006-09, Vol.99 (6), p.227-229
Main Author: Subramanian, C.R.
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An acyclic edge colouring of a graph is a proper edge colouring in which the union of any two colour classes does not contain a cycle, that is, forms a forest. It is known that there exists such a colouring using at most 16 Δ ( G ) colours where Δ ( G ) denotes the maximum degree of a graph G. However, no non-trivial constructive bound (which works for all graphs) is known except for the straightforward distance 2 colouring which requires Δ 2 colours. We analyse a simple O ( m n Δ 2 ( log Δ ) 2 ) time greedy heuristic and show that it uses at most 5 Δ ( log Δ + 2 ) colours on any graph.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2006.05.001