Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs
Felix Joos · Journal of Graph Theory · 2017
Abstract 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 vertices such that 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.