http://openproblemgarden.org/op/5_coloring_graphs_with_small_crossing_clique_numbers Comments for "5-coloring graphs with small crossing &amp; clique numbers" en http://openproblemgarden.org/op/5_coloring_graphs_with_small_crossing_clique_numbers <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/oporowski_bogdan">Oporowski</a>; <a href="/category/zhao_david">Zhao</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>For a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, we let <img class="teximage" src="/files/tex/1c88c74b39c3c8b388e8af0eb6b815eaa7a993c3.png" alt="$ cr(G) $" /> denote the <a href="http://en.wikipedia.org/wiki/Crossing number (graph theory)">crossing number</a> of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, and we let <img class="teximage" src="/files/tex/1ffde08316d085349f8e182472c09fd26e466d8e.png" alt="$ \omega(G) $" /> denote the size of the largest complete subgraph of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />. </p> <div class="envtheorem"><b>Question</b>&nbsp;&nbsp; Does every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> with <img class="teximage" src="/files/tex/a403effa182f63b08ce8a87b127d4400b86db161.png" alt="$ cr(G) \le 5 $" /> and <img class="teximage" src="/files/tex/2320b0f36ab8acdec343b9d613e16e4bab300f1f.png" alt="$ \omega(G) \le 5 $" /> have a 5-coloring? </div> </tr></td> </table> </td> </tr> </table> Oporowski, Bogdan Zhao, David coloring crossing number planar graph Graph Theory Topological Graph Theory Coloring http://openproblemgarden.org/op/5_coloring_graphs_with_small_crossing_clique_numbers#comment Tue, 09 Oct 2007 06:19:17 +0200 mdevos 644 at http://openproblemgarden.org