Non-repetitive colouring of planar and other
proper minor-closed classes of graphs
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".