pith. sign in

arxiv: 1701.07425 · v3 · pith:OXRP2ECMnew · submitted 2017-01-24 · 🧮 math.CO

Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor

classification 🧮 math.CO
keywords graphsnonrepetitiveboundedchromaticexcludingfixednumberimmersion
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.