Packing cycles through prescribed vertices

The well-known theorem of Erdős and Pósa says that a graph G has either k vertex-disjoint cycles or a vertex set X of order at most f ( k ) such that G ∖ X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimiza...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2011-09, Vol.101 (5), p.378-381
Main Authors: Kakimura, Naonori, Kawarabayashi, Ken-ichi, Marx, Dániel
Format: Article
Language:English
Subjects:
Disjoint cycles
Erdős–Pósa property
Feedback vertex sets
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The well-known theorem of Erdős and Pósa says that a graph G has either k vertex-disjoint cycles or a vertex set X of order at most f ( k ) such that G ∖ X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we generalize Erdős–Pósaʼs result to cycles that are required to go through a set S of vertices. Given an integer k and a vertex subset S (possibly unbounded number of vertices) in a given graph G, we prove that either G has k vertex-disjoint cycles, each of which contains at least one vertex of S, or G has a vertex set X of order at most f ( k ) = 40 k 2 log 2 k such that G ∖ X has no cycle that intersects S.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2011.03.004