On the presence of disjoint subgraphs of a specified type
On the presence of disjoint subgraphs of a specified type
复制标题
关于指定类型的不相交子图的存在
DOI：
10.1002/jgt.3190120111
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
C. Thomassen
中科院分区：
文献类型：
--
作者：
C. Thomassen
我们说一个图族G具有Erdos-Posa性质，如果存在一个函数f（k）使得任意图G包含k个不相交的子图，每个子图同构于G的一个成员，或者包含至多f（k）个顶点的集合S使得G-S不包含G中的图.我们推导出一族图具有Erdos-Posa性质的一般充分条件。特别地，对于任何固定的自然数m，长度可被m整除的圈的集合具有Erdos-Posa性质。作为副产品，我们得到了一个多项式有界的算法，找到一个周期的长度可除m。另一方面，我们描述了一个一般类的平面图H，这样的一个集合的细分H不具有的Erdos-Posa属性。事实上，H也可能是一棵树。
We say that a graph family ℱ has the Erdos-Posa property if there exists a function f(k) such that any graph G contains either k disjoint subgraphs each isomorphic to a member of ℱ, or contains a set S of at most f(k) vertices such that G — S contains no graph in ℱ. We derive a general sufficient condition for a family of graphs to have the Erdos-Posa property. In particular, for any fixed natural number m the collection of cycles of length divisible by m has the Erdos-Posa property. As a by-product, we obtain a polynomially bounded algorithm for finding a cycle of length divisible by m. On the other hand, we describe a general class of planar graphs H such that a collection of subdivisions of H does not have the Erdos-Posa property. In fact, H may even be a tree.