Abstract
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.
Original language | English |
---|---|
Journal | Combinatorica |
Volume | 21 |
Issue number | 2 |
Pages (from-to) | 321-333 |
ISSN | 0209-9683 |
DOIs | |
Publication status | Published - 2001 |