A tight Erdos-Posa function for long cycles

作者：Mousset F^*; Noever A; Skoric N; Weissenberger F

来源：Journal of Combinatorial Theory - Series B, 2017, 125: 21-32.

DOI：10.1016/j.jctb.2017.01.004

• Erdos-Posa property
• Covering vs packing
• Long cycles
• Graph theory

A classic result of Erdos and Posa states that any graph either contains k vertex-disjoint cycles or can be made acyclic by deleting at most O(k log k) vertices. Birmele, Bondy, and Reed (2007) raised the following more general question: given numbers l and k, what is the optimal function f(l,k) such that every graph G either contains k vertex-disjoint cycles of length at least l or contains a set X of f(l,k) vertices that meets all cycles of length at least l? In this paper, we answer that question by proving that f (l, k) = Theta(kl + k log k). As a corollary, the tree-width of any graph G that does not contain k vertex-disjoint cycles of length at least l is of order O(kl + k log k). This is also optimal up to constant factors and answers another question of Birmele, Bondy, and Reed (2007).

• 出版日期2017-7