![](/files/happy5.png)
Erdős-Posa property for long directed cycles
![$ \ell \geq 2 $](/files/tex/061b4d40c28de2de3ccfebdeeb52a6730a9cee76.png)
![$ n\geq 0 $](/files/tex/6a9c6e677c8a074e2f8306290b3acb959626d2a4.png)
![$ t_n=t_n(\ell) $](/files/tex/2ce8e7dd4d72ec3247e3b656a3e3cfa985241df5.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ \ell $](/files/tex/d2c5960dd9795a1b000a5843d282c97268e303c4.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ t_n $](/files/tex/4e1d881c711abbf6021a83fe432d28abc22d717b.png)
![$ D-T $](/files/tex/15b90efb84c80a9728144fa55150c691b4230a8a.png)
![$ \ell $](/files/tex/d2c5960dd9795a1b000a5843d282c97268e303c4.png)
The case has been proved by Reed et al. [RRST], hence solving a conjecture of Gallai [G] and Younger [Y]. The case
and
has previously been solved by McCuaig [M], who proved that
. Havet and Maia [HM] proved the case
.
The analogous statement for undirected graph has been proved by Birmelé, Bondy and Reed [BBR], hence generalizing Erdős-Posa [EP] result for .
Bibliography
[BBR] E. Birmelé, J.A. Bondy, and B.A. Reed. The Erdos-Posa property for long circuits, Combinatorica, 27(2), 135–145, 2007.
[EP] P. Erdős and L. Pósa. On the independent circuits contained in a graph. Canad. J. Math., 17, 347--352, 1965.
[G] T. Gallai. Problem 6, in Theory of Graphs, Proc. Colloq. Tihany 1966 (New York), Academic Press, p.362, 1968.
*[HM] F. Havet and A. K. Maia. On disjoint directed cycles with prescribed minimum lengths. INRIA Research Report, RR-8286, 2013.
[M] W. McCuaig, Intercyclic digraphs. Graph Structure Theory, (Neil Robertson and Paul Seymour, eds.), AMS Contemporary Math., 147:203--245, 1993.
[RRST] B. Reed, N. Robertson, P.D. Seymour, and R. Thomas. Packing directed circuits. Combinatorica, 16(4):535--554, 1996.
[Y] D. H. Younger. Graphs with interlinked directed circuits. Proceedings of the Midwest Symposium on Circuit Theory, 2:XVI 2.1 - XVI 2.7, 1973.
* indicates original appearance(s) of problem.