http://openproblemgarden.org/op/degenerate_colorings_of_planar_graphs Comments for "Degenerate colorings of planar graphs" en http://openproblemgarden.org/op/degenerate_colorings_of_planar_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/borodin_oleg_v">Borodin</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/topological_graph_theory">Topological G.T.</a> » <a href="/category/coloring_1">Coloring</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>A graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-<em>degenerate</em> if every subgraph of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> has a vertex of degree <img class="teximage" src="/files/tex/26d614fff037e5976f481eab5b4e36c487e120ac.png" alt="$ \le k $" />.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Every simple planar graph has a 5-coloring so that for <img class="teximage" src="/files/tex/8444626f9ce5a1ce2947ad77497c0627b390df33.png" alt="$ 1 \le k \le 4 $" />, the union of any <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> color classes induces a <img class="teximage" src="/files/tex/bc98477dfed13603bd35290b8c8d5cd9c5af536f.png" alt="$ (k-1) $" />-degenerate graph. </div> </tr></td> </table> </td> </tr> </table> Borodin, Oleg V. coloring degenerate planar Graph Theory Topological Graph Theory Coloring http://openproblemgarden.org/op/degenerate_colorings_of_planar_graphs#comment Wed, 21 May 2008 06:36:50 +0200 mdevos 798 at http://openproblemgarden.org