On the presence of disjoint subgraphs of a specified type
Author:
- 1 March 1988
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 12 (1) , 101-111
Abstract
We say that a graph family ℱ has the Erdös‐Pósa 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 Erdös‐Pósa property. In particular, for any fixed natural number m the collection of cycles of length divisible by m has the Erdös‐Pósa 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 Erdös‐Pósa property. In fact, H may even be a tree.Keywords
This publication has 10 references indexed in Scilit:
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986
- Graph minors. V. Excluding a planar graphJournal of Combinatorial Theory, Series B, 1986
- Sign-nonsingular matrices and even cycles in directed graphsLinear Algebra and its Applications, 1986
- On a Class of Totally Unimodular MatricesMathematics of Operations Research, 1985
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984
- Cycles in digraphs– a surveyJournal of Graph Theory, 1981
- Decomposition of regular matroidsJournal of Combinatorial Theory, Series B, 1980
- The directed subgraph homeomorphism problemTheoretical Computer Science, 1980
- On Independent Circuits Contained in a GraphCanadian Journal of Mathematics, 1965
- Additivity of the genus of a graphBulletin of the American Mathematical Society, 1962