Skip to main content
Source Link
Gil Kalai
  • 25.2k
  • 40
  • 248
  • 340

Closely related conjectures are the following: 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 who further conjectured that five colours always suffice with the additional condition that the union of every $k$ colour classes, $1 \le k \le 4$ induces a $(k-1)$-degenerate graph.

Post Made Community Wiki by Gil Kalai