http://openproblemgarden.org/op/alon_saks_seymour_conjecture Comments for "Alon-Saks-Seymour Conjecture" en http://openproblemgarden.org/op/alon_saks_seymour_conjecture#comment-6712 <p>Hao Huang and Benny Sudakov have found a fascinating counterexample to this conjecture. Their paper can be found on the arxiv <a href="http://arxiv.org/abs/1002.4687">here</a></p> Fri, 26 Feb 2010 19:54:45 +0100 mdevos comment 6712 at http://openproblemgarden.org http://openproblemgarden.org/op/alon_saks_seymour_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/alon">Alon</a>; <a href="/category/saks_mike">Saks</a>; <a href="/category/seymour">Seymour</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/coloring">Coloring</a> » <a href="/category/vertex_coloring">Vertex coloring</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a simple graph which can be written as an union of <img class="teximage" src="/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png" alt="$ m $" /> edge-disjoint complete bipartite graphs, then <img class="teximage" src="/files/tex/0aefe0f752ac272776eec5c61c7d1a1822a3d224.png" alt="$ \chi(G) \le m+1 $" />. </div> </tr></td> </table> </td> </tr> </table> Alon, Noga Saks, Michael Seymour, Paul D. coloring complete bipartite graph eigenvalues interlacing Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/alon_saks_seymour_conjecture#comment Mon, 28 May 2007 06:52:02 +0200 mdevos 342 at http://openproblemgarden.org