Open Problem Garden - Odd-cycle transversal in triangle-free graphs - Comments

Open Problem Garden - Odd-cycle transversal in triangle-free graphs - Comments http://openproblemgarden.org/op/odd_cycle_transversal_in_triangle_free_graphs Comments for "Odd-cycle transversal in triangle-free graphs" en Odd-cycle transversal in triangle-free graphs http://openproblemgarden.org/op/odd_cycle_transversal_in_triangle_free_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/erdos">Erdos</a>; <a href="/category/faudree_ralph">Faudree</a>; <a href="/category/pach_janos">Pach</a>; <a href="/category/spencer_joel">Spencer</a>   </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/extremal_graph_theory">Extremal G.T.</a>   </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>   If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a simple triangle-free graph, then there is a set of at most <img class="teximage" src="/files/tex/0db5eaf8ff84c2da58a206455442346f6fa11c19.png" alt="$ n^2/25 $" /> edges whose deletion destroys every odd cycle. </div> </tr></td> </table> </td> </tr> </table> Erdos, Paul Faudree, Ralph Pach, János Spencer, Joel Graph Theory Extremal Graph Theory http://openproblemgarden.org/op/odd_cycle_transversal_in_triangle_free_graphs#comment Wed, 06 Mar 2013 04:14:13 +0100 fhavet 46824 at http://openproblemgarden.org