Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
arXiv:1701.07425 · doi:10.1002/jgt.22430
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.
References in corpus (6)
- Characterisations and Examples of Graph Classes with Bounded Expansion
- Nonrepetitive Colouring via Entropy Compression
- Layered Separators in Minor-Closed Graph Classes with Applications
- A new approach to nonrepetitive sequences
- Vertex coloring of plane graphs with nonrepetitive boundary paths
- Nonrepetitive Colourings of Planar Graphs with Colours