Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor

DOI10.1002/JGT.22430zbMATH Open1417.05080arXiv1701.07425OpenAlexW3103477445MaRDI QIDQ5229534FDOQ5229534

Paul Wollan, David R. Wood

Publication date: 15 August 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1701.07425

zbMATH Keywords

graph coloringimmersiontopological minornonrepetitive coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Cited In (1)

• A note on the immersion number of generalized Mycielski graphs

This page was built for publication: Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229534)