Packing topological minors half‐integrally
Packing topological minors half‐integrally
复制标题
将拓扑次要部分封装成半积分
DOI：
10.1112/jlms.12633
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Liu, Chun‐Hung
中科院分区：
文献类型：
--
作者：
Liu, Chun‐Hung
The packing problem and the covering problem are two of the most general questions in graph theory. The Erdős–Pósa property characterizes the cases when the optimal solutions of these two problems are bounded by functions of each other. Robertson and Seymour proved that when packing and covering H$H$‐minors for any fixed graph H$H$, the planarity of H$H$ is equivalent to the Erdős–Pósa property. Thomas conjectured that the planarity is no longer required if the solution of the packing problem is allowed to be half‐integral. In this paper, we prove that this half‐integral version of Erdős–Pósa property holds for packing and covering H$H$‐topological minors, for any fixed graph H$H$, which easily implies Thomas' conjecture. In fact, we prove an even stronger statement in which those topological minors are rooted at any choice of prescribed subsets of vertices. A number of results on H$H$‐topological minor‐free or H$H$‐minor‐free graphs have conclusions or requirements tied to properties of H$H$. Classes of graphs that can half‐integrally pack only a bounded number of H$H$‐topological minors or H$H$‐minors are more general topological minor‐closed or minor‐closed families whose minimal obstructions are more complicated than H$H$. Our theorem provides a general machinery to extend those results to those more general classes of graphs without losing their tight connections to H$H$.
登录
查看更多内容
DOI：
10.1016/j.jctb.2008.08.003
发表时间：
2009
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour
DOI：
10.1016/s0304-0208(08)73486-8
发表时间：
1982
期刊：
North-holland Mathematics Studies
影响因子：
--
作者：
L. Babai;F. Chung;P. Erdös;R. Graham;J. Spencer
通讯作者：
L. Babai;F. Chung;P. Erdös;R. Graham;J. Spencer
穿刺 d 间隔
影响因子：
0.8
作者：
N. Alon
通讯作者：
N. Alon
DOI：
--
发表时间：
2003
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour
图未成年人.XII。
DOI：
--
发表时间：
1995
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour