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...
Saved in:
Published in: | Information processing letters 2006-09, Vol.99 (6), p.227-229 |
---|---|
Main Author: | |
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!
|
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 |