Acyclic colourings of graphs with bounded degree
Mieczysław Borowiecki, Anna Fiedorowicz, Katarzyna Jesse-Józefczyk, Elżbieta Sidorowicz
Abstract
A k-colouring of a graph G is called
acyclic
if for every two distinct colours i and j,
the
subgraph induced in G by all the edges linking a vertex
coloured
with i and a vertex coloured with j is
acyclic.
In other words, there are no bichromatic alternating cycles. In 1999
Boiron
et al. conjectured that a graph G with maximum
degree
at most 3 has an acyclic 2-colouring such that the set of vertices in
each
colour induces a subgraph with maximum degree at most 2. In this paper
we
prove this conjecture and show that such a colouring of a cubic graph
can
be determined in polynomial time. We also prove that it is an
NP-complete
problem to decide if a graph with maximum degree 4 has the above
mentioned colouring.
Full Text: PDF PostScript