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 -