http://openproblemgarden.org/op/seymours_r_graph_conjecture Comments for "Seymour's r-graph conjecture" en http://openproblemgarden.org/op/seymours_r_graph_conjecture <table cellspacing="10"> <tr> <td> Author(s): <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/edge_coloring">Edge coloring</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>An <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-<em>graph</em> is an <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-regular graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> with the property that <img class="teximage" src="/files/tex/65007ad8f8ee468c7faf3f5f882149101879b9dc.png" alt="$ |\delta(X)| \ge r $" /> for every <img class="teximage" src="/files/tex/96b9bd6b2f86ef63d6baa3de4061413cf38394f0.png" alt="$ X \subseteq V(G) $" /> with odd size.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; <img class="teximage" src="/files/tex/efa38d9230a3451d1c38c061522cb607572d369b.png" alt="$ \chi&#039;(G) \le r+1 $" /> for every <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />. </div> </tr></td> </table> </td> </tr> </table> Seymour, Paul D. edge-coloring r-graph Graph Theory Coloring Edge coloring http://openproblemgarden.org/op/seymours_r_graph_conjecture#comment Fri, 03 Oct 2008 01:23:17 +0200 mdevos 2226 at http://openproblemgarden.org