http://openproblemgarden.org/op/separators_in_string_graphs Comments for "Separators in string graphs" en http://openproblemgarden.org/op/separators_in_string_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/fox_jacob">Fox</a>; <a href="/category/pach_janos">Pach</a>; <a href="/category/toth_csaba_d">Tóth</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; Every string graph with <img class="teximage" src="/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png" alt="$ m $" /> edges has a separator of size <img class="teximage" src="/files/tex/01ec492c9e4186fd59ffcc3c03daf4f86366b7db.png" alt="$ O(\sqrt{m}) $" />. </div> </tr></td> </table> </td> </tr> </table> Fox, Jacob Pach, János Tóth, Csaba D. separator string graphs Graph Theory http://openproblemgarden.org/op/separators_in_string_graphs#comment Fri, 01 Jan 2010 11:30:09 +0100 cibulka 37176 at http://openproblemgarden.org