Journal article
The Erdos-Posa property for odd cycles in graphs of large connectivity
A graph G is k-linked if G has at least 2k vertices, and, for any vertices x(1), x(2), ..., x(k), y(1), y(2), ..., y(k), G colltains b pairwise disjoint paths P-1, P-2, ..., P-k such that P-i joins x(i), y(i) for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths P-1, P-2, ..., P-k call be chosen such that the parities of their lengths are prescribed.
We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of ally set of less than 4k - 3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdos-Posa type for odd cycles in graphs of large connectivity Also, every 2(3162)-connected graph contains a totally odd K-4-subdivision, that is, a subdivision of K-4 in which each edge of K-4 corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph.
Language: | English |
---|---|
Publisher: | Bolyai Society – Springer-Verlag |
Year: | 2001 |
Pages: | 321-333 |
Journal subtitle: | An International Journal on Combinatorics and the Theory of Computing |
ISSN: | 02099683 and 14396912 |
Types: | Journal article |
DOI: | 10.1007/s004930100028 |
ORCIDs: | Thomassen, Carsten |