Tight bound for the Erdős-Pósa property of tree minors

CoRR(2024)

引用 0|浏览6
暂无评分
摘要
Let T be a tree on t vertices. We prove that for every positive integer k and every graph G, either G contains k pairwise vertex-disjoint subgraphs each having a T minor, or there exists a set X of at most t(k-1) vertices of G such that G-X has no T minor. The bound on the size of X is best possible and improves on an earlier f(t)k bound proved by Fiorini, Joret, and Wood (2013) with some very fast growing function f(t). Moreover, our proof is very short and simple.
更多
查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要