The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Combinatorica - Tập 21 - Trang 267-278 - 2001
Dieter Rautenbach1, Bruce Reed2
1Equipe Combinatoire, Université Pierre et Marie Curie; 75013 Paris, France; E-mail: [email protected], , DE
2Equipe Combinatoire, Université Pierre et Marie Curie; 75013 Paris, France, E-mail: [email protected], , FR

Tóm tắt

In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible.