http://openproblemgarden.org/op/the_erdos_hajnal_conjecture Comments for "The Erdös-Hajnal Conjecture" en http://openproblemgarden.org/op/the_erdos_hajnal_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/erdos">Erdos</a>; <a href="/category/hajnal">Hajnal</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/extremal_graph_theory">Extremal G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For every fixed graph <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" />, there exists a constant <img class="teximage" src="/files/tex/f3109c2657867bfbf5df1f9d878be062ffaa82d0.png" alt="$ \delta(H) $" />, so that every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> without an induced subgraph isomorphic to <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> contains either a clique or an independent set of size <img class="teximage" src="/files/tex/e12fe74b562523df4457275a178e2078c43c7715.png" alt="$ |V(G)|^{\delta(H)} $" />. </div> </tr></td> </table> </td> </tr> </table> Erdos, Paul Hajnal, Andras induced subgraph Graph Theory Extremal Graph Theory http://openproblemgarden.org/op/the_erdos_hajnal_conjecture#comment Sun, 18 Mar 2007 11:50:01 +0100 mdevos 162 at http://openproblemgarden.org