http://www.openproblemgarden.org/op/melnikovs_valency_variety_problem Comments for "Melnikov's valency-variety problem" en http://www.openproblemgarden.org/op/melnikovs_valency_variety_problem <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/melnikov_l_s">Melnikov</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>Problem</b>&nbsp;&nbsp; The valency-variety <img class="teximage" src="/files/tex/a1ba1262a44dc4c4c585e3e1854ea2218cd40629.png" alt="$ w(G) $" /> of a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is the number of different degrees in <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />. Is the chromatic number of any graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> with at least two vertices greater than <img class="teximage" src="/files/tex/90d7d0498914cd55d9d67b5608aa716bfcb06880.png" alt="$$\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$$" /> </div> </tr></td> </table> </td> </tr> </table> Melnikov, L. S. Graph Theory Coloring Vertex coloring http://www.openproblemgarden.org/op/melnikovs_valency_variety_problem#comment Sun, 03 Mar 2013 22:24:17 +0100 asp 46575 at http://www.openproblemgarden.org