http://openproblemgarden.org/op/crossing_numbers_and_coloring Comments for "Crossing numbers and coloring" en http://openproblemgarden.org/op/crossing_numbers_and_coloring <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/albertson_michael_o">Albertson</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/crossing_numbers">Crossing numbers</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>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 a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> with <img class="teximage" src="/files/tex/cb74f630a3b502fe0bd0726e72880c005ec02d22.png" alt="$ \chi(G) \ge t $" /> satisfies <img class="teximage" src="/files/tex/64703b245f27999c87b0a8e3c56c14e80f1925d4.png" alt="$ cr(G) \ge cr(K_t) $" />. </div> </tr></td> </table> </td> </tr> </table> Albertson, Michael O. coloring complete graph crossing number Graph Theory Topological Graph Theory Crossing numbers http://openproblemgarden.org/op/crossing_numbers_and_coloring#comment Fri, 04 Sep 2009 07:21:18 +0200 mdevos 37068 at http://openproblemgarden.org