TY - JOUR

T1 - Packing cycles through prescribed vertices

AU - Kakimura, Naonori

AU - Kawarabayashi, Ken ichi

AU - Marx, Dániel

N1 - Funding Information:
E-mail addresses: kakimura@mist.i.u-tokyo.ac.jp (N. Kakimura), k_keniti@nii.ac.jp (K.-i. Kawarabayashi), dmarx@cs.bme.hu (D. Marx). 1 Partly supported by the Grant-in-Aid for Scientific Research and by the Global COE Program “The research and training center for new development in mathematics.” 2 Partly supported by the Japan Society for the Promotion of Science, by the Grant-in-Aid for Scientific Research, by the C & C Foundation, by the Kayamori Foundation and by the Inoue Research Award for Young Scientists. 3 Partly supported by the Alexander von Humboldt Foundation, by the ERC Advanced Grant DMMCA, and by the Hungarian National Research Fund (OTKA 67651).

PY - 2011/9

Y1 - 2011/9

N2 - The well-known theorem of Erdo{double acute accent}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 Erdo{double acute accent}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)=40k2log2k such that G\X has no cycle that intersects S.

AB - The well-known theorem of Erdo{double acute accent}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 Erdo{double acute accent}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)=40k2log2k such that G\X has no cycle that intersects S.

KW - Disjoint cycles

KW - Erdo{double acute accent}s-Pósa property

KW - Feedback vertex sets

UR - http://www.scopus.com/inward/record.url?scp=79956259717&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79956259717&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2011.03.004

DO - 10.1016/j.jctb.2011.03.004

M3 - Article

AN - SCOPUS:79956259717

SN - 0095-8956

VL - 101

SP - 378

EP - 381

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 5

ER -