The Erdős-Pósa property for odd cycles in highly connected graphs (Q5955201)

From MaRDI portal
scientific article; zbMATH DE number 1703950
Language Label Description Also known as
English
The Erdős-Pósa property for odd cycles in highly connected graphs
scientific article; zbMATH DE number 1703950

    Statements

    The Erdős-Pósa property for odd cycles in highly connected graphs (English)
    0 references
    0 references
    0 references
    13 February 2002
    0 references
    An \(f(k)\)-connected graph either contains \(k\) vertex-disjoint odd cycles or an odd cycle cover containing at most \(2k-2\) vertices. This result was proved by \textit{C. Thomassen} [Combinatorica 21, 321-333 (2001)] with a doubly exponential \(f(k)\). The authors prove it with \(f(k)=576k\) and show that this is ``essentially best possible''.
    0 references
    Erdős-Pósa property
    0 references
    highly connected graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references