To Cheer You Up in Difficult times 24: Borodin’s colouring conjecture!

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 $r$-degenerate if every subgraph has a vertex of degree at most $r$.

Every planar graph G can be coloured with five colours so that the union of every k colour classes, $1 \le k \le 4$ 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, $1 \le k \le 4$ induces a stress free graph for generic embedding into $R^{k-1}$.

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.

This entry was posted in Combinatorics and tagged , . Bookmark the permalink.