Non-repetitive colouring of planar and other
proper minor-closed classes of graphs

We show that any $n$-vertex planar graph, or more generally any graph from a proper minor closed class of graphs, has a non-repetitive chromatic number at most $O(\log n)$. The best previous bound was $O(n^\frac{1}{2})$. The proof uses, so called, "layered separators". These separators may have linear size in $n$, but have bounded size with respect to a different measure, called the "breadth".