http://openproblemgarden.org/op/complete_bipartite_subgraphs_of_perfect_graphs Comments for "Complete bipartite subgraphs of perfect graphs" en http://openproblemgarden.org/op/complete_bipartite_subgraphs_of_perfect_graphs#comment-93658 <p>In this recent preprint on Paul Seymour's webpage: http://web.math.princeton.edu/~pds/papers/pure5/paper.pdf (not on ArXiv nor published yet)</p> Tue, 19 Jan 2021 14:32:20 +0100 Anonymous comment 93658 at http://openproblemgarden.org http://openproblemgarden.org/op/complete_bipartite_subgraphs_of_perfect_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/fox_jacob">Fox</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/basic_graph_theory">Basic G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a perfect graph on <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> vertices. Is it true that either <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> or <img class="teximage" src="/files/tex/1e3dac00cfbbb43d9181a85bc8a5389e16490552.png" alt="$ \bar{G} $" /> contains a complete bipartite subgraph with bipartition <img class="teximage" src="/files/tex/e0150654d2f6aa6b2ea50e726af4747878a605fc.png" alt="$ (A,B) $" /> so that <img class="teximage" src="/files/tex/457f19bbb97576457ac692bc6acdd4ac8e9f39a1.png" alt="$ |A|, |B| \ge n^{1 - o(1)} $" />? </div> </tr></td> </table> </td> </tr> </table> Fox, Jacob perfect graph Graph Theory Basic Graph Theory http://openproblemgarden.org/op/complete_bipartite_subgraphs_of_perfect_graphs#comment Tue, 17 Jun 2008 20:27:38 +0200 mdevos 826 at http://openproblemgarden.org