Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor

Abstract

We prove that graphs excluding a fixed immersion have bounded nonrepetitive chromatic number. More generally, we prove that if $H$ 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 $H$ as a topological minor have bounded nonrepetitive chromatic number. This is the largest class of graphs known to have bounded nonrepetitive chromatic number.

References in corpus (1)

• Layered Separators in Minor-Closed Graph Classes with Applications

Cited by in corpus (1)

• Nonrepetitive graph colouring