The structure of graphs not admitting a fixed immersion
The structure of graphs not admitting a fixed immersion
复制标题
DOI：
10.1016/j.jctb.2014.07.003
复制
发表时间：
2015-01-01
影响因子：
1.4
通讯作者：
Wollan, Paul
中科院分区：
文献类型：
--
作者：
Wollan, Paul
对于不允许完全图K-t浸入的图，我们给出了一个简单的结构定理。该定理激发了基于边割而不是顶点割的树分解的变体的定义，我们称之为树割分解。本文给出了树割分解的宽度的定义，并利用这个定义沿着与排除团浸入的结构定理，证明了每个图要么有界树割宽度，要么允许一个大的浸入墙. (C)2014爱思唯尔公司All rights reserved.
We present an easy structure theorem for graphs which do not admit an immersion of the complete graph K-t. The theorem motivates the definition of a variation of tree decompositions based on edge cuts instead of vertex cuts which we call tree-cut decompositions. We give a definition for the width of tree-cut decompositions, and using this definition along with the structure theorem for excluded clique immersions, we prove that every graph either has bounded tree-cut width or admits an immersion of a large wall. (C) 2014 Elsevier Inc. All rights reserved.