Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor. Issue 3 (19th November 2018)

• Record Type: Journal Article
• Authors: Wollan, Paul; Wood, David R.
• Is Part Of: Journal of graph theory. Volume 91:Issue 3(2019)
• Page Start: 259
• Page End: 266
• Publication Date: 2018-11-19
• Subjects: graph coloring -- immersion -- nonrepetitive coloring -- topological minor; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22430
• Languages: English
• ISSNs: 0364-9024

Abstract

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.