An acyclic colouring of a graph is a colouring of its vertices so that the subgraph spanned on union of every two colour classes is acyclic (a forest). Grunbaum conjectured in 1973 that

**Every planar graph has acyclic colouring with five colours. **

This was proved by Borodin in 1976.

Borodin made the following stronger conjecture. Recall that a graph is -degenerate if every subgraph has a vertex of degree at most .

**Every planar graph ***G* can be coloured with five colours so that the union of every *k* colour classes, induces a *(k-1)*-degenerate graph.

Let me mention an intermediate conjecture in-between Grunbaum’s conjecture and Borodin’s

**Every planar graph ***G* can be coloured with five colours so that the union of every *k* colour classes, induces a stress free graph for generic embedding into .

Grunbaum’s 1973 paper Acyclic** **colorings of planar graphs is a very imaginative and highly cited paper. It was the first paper I ever refereed and I remember spending a lot of time reading it. Here is the link to Borodin’s paper On acyclic colorings of planar graphs. I am not sure what is the current world-record for the number of colours.

### Like this:

Like Loading...

*Related*