http://openproblemgarden.org/op/erdos_posa_property_for_long_directed_cycles Comments for "Erdős-Posa property for long directed cycles" en http://openproblemgarden.org/op/erdos_posa_property_for_long_directed_cycles <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/havet_frederic">Havet</a>; <a href="/category/maia_ana_karolinna">Maia</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/directed_graphs">Directed Graphs</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/061b4d40c28de2de3ccfebdeeb52a6730a9cee76.png" alt="$ \ell \geq 2 $" /> be an integer. For every integer <img class="teximage" src="/files/tex/6a9c6e677c8a074e2f8306290b3acb959626d2a4.png" alt="$ n\geq 0 $" />, there exists an integer <img class="teximage" src="/files/tex/2ce8e7dd4d72ec3247e3b656a3e3cfa985241df5.png" alt="$ t_n=t_n(\ell) $" /> such that for every digraph <img class="teximage" src="/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png" alt="$ D $" />, either <img class="teximage" src="/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png" alt="$ D $" /> has a <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> pairwise-disjoint directed cycles of length at least <img class="teximage" src="/files/tex/d2c5960dd9795a1b000a5843d282c97268e303c4.png" alt="$ \ell $" />, or there exists a set <img class="teximage" src="/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png" alt="$ T $" /> of at most <img class="teximage" src="/files/tex/4e1d881c711abbf6021a83fe432d28abc22d717b.png" alt="$ t_n $" /> vertices such that <img class="teximage" src="/files/tex/15b90efb84c80a9728144fa55150c691b4230a8a.png" alt="$ D-T $" /> has no directed cycles of length at least <img class="teximage" src="/files/tex/d2c5960dd9795a1b000a5843d282c97268e303c4.png" alt="$ \ell $" />. </div> </tr></td> </table> </td> </tr> </table> Havet, Frédéric Maia, Ana Karolinna Graph Theory Directed Graphs http://openproblemgarden.org/op/erdos_posa_property_for_long_directed_cycles#comment Tue, 25 Jun 2013 20:30:21 +0200 fhavet 52200 at http://openproblemgarden.org