**Zdeněk Dvořák**

Charles University, Prague

Colouring the square of a graph naturally arises in connection
with the distance labelings, which have been studied intensively. We consider
the problem
for sparse subcubic graphs.
We show that the choosability
of the square of a subcubic
graph
of maximum average degree is at most four if and does not
contain a 5-cycle,
is at most five if and
at most six if
.
Wegner's conjectures claims that the chromatic number of the square of a
subcubic planar graph
is at most seven. Our result implies that
is at most four if
, it is at most if and it is at most if .
For lower bounds,
we find a planar subcubic graph of girth such that
and a planar
subcubic graph of girth five such that . As a
consequence, we show
that the problem of -colouring of the square of a subcubic planar graph of
girth
is NP-complete.

2005-05-23