A stronger structure theorem for excluded topological minors
A stronger structure theorem for excluded topological minors
复制标题
排除拓扑次要的更强结构定理
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Zdenek Dvorák
中科院分区：
文献类型：
--
作者：
Zdenek Dvorák
Grohe 和 Marx 证明，如果 G 不包含 H 作为拓扑次要，则存在常数 g=O(|V(H)|^4)、D 和 t 仅取决于 H，使得 G 是图的团和，该图要么包含至多 t 个度数大于 D 的顶点，要么几乎嵌入到最多 g 的属的某个表面中。我们强化了这个结果，对后一种分解的基本图给出了更精确的描述——我们只允许（几乎）以 H 不可能的方式嵌入的图（类似于次要的结构定理，其中只允许几乎嵌入到 H 不嵌入的表面中的图）。这使我们能够给出图的结构结果，避免使用固定图作为沉浸，以及具有有界无限可允许性的图。
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.
排除拓扑子图的图的结构定理和同构检验
DOI：
10.1145/2213977.2213996
发表时间：
2012
期刊：
影响因子：
--
作者：
M. Grohe;D. Marx
通讯作者：
D. Marx