Premium
On the presence of disjoint subgraphs of a specified type
Author(s) -
Thomassen Carsten
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120111
Subject(s) - combinatorics , mathematics , disjoint sets , discrete mathematics , bounded function , graph , cograph , pathwidth , line graph , mathematical analysis
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.