Parity Linkage and the Erdos-Posa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs

摘要

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 Erds-Posa 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. (C) 2017 Wiley Periodicals, Inc.