2014/11/24 by Felix Joos, Joos, Felix
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #math.CO
paper · pdf · doi:10.48550/arxiv.1411.6554
12 pages, referees' comments incorporated
openalex publication_date 2014/11/24 · arxiv created 2016/02/16 · arxiv updated 2016/02/17 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
We show the following for every sufficiently connected graph G, any vertex subset S of G, and given integer k: there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most 2k-2 vertices such that G-X does not contain any odd cycle that contains a vertex of S. We prove this via an extension of Kawarabayashi and Reed's result about parity-k-linked graphs (Combinatorica 29, 215-225). From this result it is easy to deduce several other well known results about the Erdős-Pósa property of odd cycles in highly connected graphs. This strengthens results due to Thomassen (Combinatorica 21, 321-333), and Rautenbach and Reed (Combinatorica 21, 267-278), respectively.