ALCOMFT-TR-03-171

Maria Andreou and Paul Spirakis
Efficient Colouring of Squares of Planar Graphs
Patras. Work packages 2 and 4. December 2003.

Abstract: In this work we provide a new colouring algorithm, which colours the square of any planar graph G using at most 1.5 \D(G) + c colours, where c <= 26, and the maximum degree of G (i.e. \D(G)) is greater than 8.

In 1977 Wegner conjectured the above bound for c = 1 in [W77]. The best currently known upper bound for the chromatic number of the square of G is 1.66 \D(G) + 24 due to Molloy and Salavatipour [MS02].

Postscript file: ALCOMFT-TR-03-171.ps.gz (662 kb).