pith. machine review for the scientific record. sign in

arxiv: 1209.0129 · v1 · submitted 2012-09-01 · 🧮 math.CO · cs.DM

Recognition: unknown

A stronger structure theorem for excluded topological minors

Authors on Pith no claims yet
classification 🧮 math.CO cs.DM
keywords graphsalmostembedonlycontainminorsstructuretheorem
0
0 comments X
read the original abstract

Grohe and Marx proved that if G does not contain H as a topological minor, then there exist constants g=O(|V(H)|^4), D and t depending only on H such that G is a clique sum of graphs that either contain at most t vertices of degree greater than D or almost embed in some surface of genus at most g. We strengthen this result, giving a more precise description of the latter kind of basic graphs of the decomposition - we only allow graphs that (almost) embed in ways that are impossible for H (similarly to the structure theorem for minors, where only graphs almost embedded in surfaces in that H does not embed are allowed). This enables us to give structural results for graphs avoiding a fixed graph as an immersion and for graphs with bounded infinity-admissibility.

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.