Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor
Paul Wollan, David R. Wood · Journal of Graph Theory · 2018
Abstract We prove that graphs excluding a fixed immersion have bounded nonrepetitive chromatic number. More generally, we prove that if is a fixed planar graph that has a planar embedding with all the vertices with degree at least 4 on a single face, then graphs excluding as a topological minor have bounded nonrepetitive chromatic number. This is the largest class of graphs known to have bounded nonrepetitive chromatic number.