Tight bound for the Erdős-Pósa property of tree minors
CoRR(2024)
摘要
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
正在生成论文摘要