http://openproblemgarden.org/op/hitting_every_large_maximal_clique_with_a_stable_set Comments for "Hitting every large maximal clique with a stable set" en http://openproblemgarden.org/op/hitting_every_large_maximal_clique_with_a_stable_set <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/king_andrew_d">King</a>; <a href="/category/rabern_l">Rabern</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 a universal constant <img class="teximage" src="/files/tex/b1b64614e8f5ba1571715ad1ac108f193e820416.png" alt="$ \epsilon&gt;0 $" /> such that every graph contains a stable set which intersects every maximal clique of size <img class="teximage" src="/files/tex/eab2194a527611df5ba3167fc87784074544117b.png" alt="$ (1-\epsilon)(\Delta+1) $" />.</p> </div> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Every graph contains a stable set which intersects every maximal clique of size <img class="teximage" src="/files/tex/8e59572a67c169e0fea8e361a598a18e90e5ca2f.png" alt="$ &gt;\frac{2}{3}(\Delta+1) $" />. </div> </tr></td> </table> </td> </tr> </table> King, Andrew D. Rabern, L. independent set maximal clique Graph Theory http://openproblemgarden.org/op/hitting_every_large_maximal_clique_with_a_stable_set#comment Thu, 31 Mar 2011 15:45:04 +0200 Andrew King 37308 at http://openproblemgarden.org