Parity linkage and the Erdős-Pósa property of odd cycles through prescribed vertices in highly connected graphs

preprint2016arXivOpen access

Abstract

We show the following for every sufficiently connected graph GG, any vertex subset SS of GG, and given integer kk: there are kk disjoint odd cycles in GG each containing a vertex of SS or there is set XX of at most 2k−22k-2 vertices such that G−XG-X does not contain any odd cycle that contains a vertex of SS. We prove this via an extension of Kawarabayashi and Reed's result about parity-kk-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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.