http://openproblemgarden.org/op/behzads_conjecture Comments for "Total Colouring Conjecture" en http://openproblemgarden.org/op/behzads_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/behzad_m">Behzad</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/coloring">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; A total coloring of a graph <img class="teximage" src="/files/tex/5969f28fd067291799f25ca43b6642feb6b04bd0.png" alt="$ G = (V,E) $" /> is an assignment of colors to the vertices and the edges of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, <img class="teximage" src="/files/tex/4d8024494319d0e76af12afcb2a91ab6da7fd624.png" alt="$ \chi&#039;&#039;(G) $" />, equals the minimum number of colors needed in a total coloring of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />. It is an old conjecture of Behzad that for every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, the total chromatic number equals the maximum degree of a vertex in <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, <img class="teximage" src="/files/tex/d5a9ad6f3868c26f7d6335f8f80abeb077e281e7.png" alt="$ \Delta(G) $" /> plus one or two. In other words, <img class="teximage" src="/files/tex/d4ea30e930ec20e02c5a03c6322e6d99a6bdb63a.png" alt="\[\chi&#039;&#039;(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]" /> </div> </tr></td> </table> </td> </tr> </table> Behzad, M. Total coloring Graph Theory Coloring http://openproblemgarden.org/op/behzads_conjecture#comment Wed, 04 Jun 2008 13:26:48 +0200 Iradmusa 815 at http://openproblemgarden.org