2009 Discrete Maths Seminar - 01

We consider the problem of colouring the planar map given by the Voronoi tessellation corresponding to a Poisson process in R^2. We seek deterministic colouring rules that are independent of the coordinate system (formally: isometry covariant and are factors of the Poisson process). We prove that 6 colours suffice. I shall also discuss other dimensions. With Benjamini, Gurel-Gurevich, Meyerovitch, Peled.