首页   按字顺浏览 期刊浏览 卷期浏览 On the presence of disjoint subgraphs of a specified type
On the presence of disjoint subgraphs of a specified type

 

作者: Carsten Thomassen,  

 

期刊: Journal of Graph Theory  (WILEY Available online 1988)
卷期: Volume 12, issue 1  

页码: 101-111

 

ISSN:0364-9024

 

年代: 1988

 

DOI:10.1002/jgt.3190120111

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractWe say that a graph family ℱ has the Erdös‐Pósa property if there exists a functionf(k) such that any graphGcontains eitherkdisjoint subgraphs each isomorphic to a member of ℱ, or contains a setSof at mostf(k) vertices such thatG — Scontains no graph in ℱ. We derive a general sufficient condition for a family of graphs to have the Erdös‐Pósa property. In particular, for any fixed natural numbermthe collection of cycles of length divisible bymhas the Erdös‐Pósa property. As a by‐product, we obtain a polynomially bounded algorithm for finding a cycle of length divisible bym. On the other hand, we describe a general class of planar graphsHsuch that a collection of subdivisions ofHdoes not have the Erdös‐Pósa property. In

 

点击下载:  PDF (591KB)



返 回