The Erdos-Posa property for odd cycles in graphs of large connectivity

    Research output: Contribution to journalJournal articleResearchpeer-review

    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 languageEnglish
    JournalCombinatorica
    Volume21
    Issue number2
    Pages (from-to)321-333
    ISSN0209-9683
    DOIs
    Publication statusPublished - 2001

    Fingerprint

    Dive into the research topics of 'The Erdos-Posa property for odd cycles in graphs of large connectivity'. Together they form a unique fingerprint.

    Cite this