Minors of two-connected graphs of large path-width
Minors of two-connected graphs of large path-width
复制标题
大路径宽度的二连通图的次数
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Thomas
中科院分区：
文献类型：
--
作者：
Thanh N. Dang;R. Thomas
设$P$是一个顶点为$v$的图，使得$P $ack $v$是一个森林，$Q$是一个外平面图。本文证明了存在一个数p=p（P，Q）$使得每个路宽至少为p$的2-连通图都有一个同构于P$或Q$的子图。这个结果回答了Seymour的一个问题，并暗示了马歇尔和Wood的一个猜想.证明是基于树分解的一个新的属性。
Let $P$ be a graph with a vertex $v$ such that $Packslash v$ is a forest, and let $Q$ be an outerplanar graph. We prove that there exists a number $p=p(P,Q)$ such that every 2-connected graph of path-width at least $p$ has a minor isomorphic to $P$ or $Q$. This result answers a question of Seymour and implies a conjecture of Marshall and Wood. The proof is based on a new property of tree-decompositions.