Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor

Paul Wollan, David R Wood

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)259-266
Number of pages8
JournalJournal of Graph Theory
Volume91
Issue number3
DOIs
Publication statusPublished - 2019

Keywords

  • graph coloring
  • immersion
  • nonrepetitive coloring
  • topological minor

Cite this