http://www.openproblemgarden.org/op/lovasz_path_removal_conjecture Comments for "Lovász Path Removal Conjecture" en http://www.openproblemgarden.org/op/lovasz_path_removal_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/lovasz">Lovasz</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; There is an integer-valued function <img class="teximage" src="/files/tex/e055b3867e7cb3cc4b2f50739eedda7657999214.png" alt="$ f(k) $" /> such that if <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is any <img class="teximage" src="/files/tex/e055b3867e7cb3cc4b2f50739eedda7657999214.png" alt="$ f(k) $" />-connected graph and <img class="teximage" src="/files/tex/e7ba5befcaa0d78e43b5176d70ce67425fd0fcdc.png" alt="$ x $" /> and <img class="teximage" src="/files/tex/739107c42bdb8452402d548efae98c3ce282847d.png" alt="$ y $" /> are any two vertices of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, then there exists an induced path <img class="teximage" src="/files/tex/b2b0b759db4d5a1b3204c38cdee6d9bd9e0d0dab.png" alt="$ P $" /> with ends <img class="teximage" src="/files/tex/e7ba5befcaa0d78e43b5176d70ce67425fd0fcdc.png" alt="$ x $" /> and <img class="teximage" src="/files/tex/739107c42bdb8452402d548efae98c3ce282847d.png" alt="$ y $" /> such that <img class="teximage" src="/files/tex/bd2b9bf16f8af17c6055284618c19085091cafd4.png" alt="$ G-V(P) $" /> is <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-connected. </div> </tr></td> </table> </td> </tr> </table> Lovasz, Laszlo Graph Theory http://www.openproblemgarden.org/op/lovasz_path_removal_conjecture#comment Mon, 04 Mar 2013 08:46:24 +0100 fhavet 46629 at http://www.openproblemgarden.org