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.
Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor / Wollan, P.; Wood, D. R.. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 91:3(2019), pp. 259-266. [10.1002/jgt.22430]
Nonrepetitive colorings of graphs excluding a fixed immersion or topological minor
Wollan P.;
2019
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.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
