http://openproblemgarden.org/op/colouring_the_square_of_a_planar_graph Comments for "Colouring the square of a planar graph" en http://openproblemgarden.org/op/colouring_the_square_of_a_planar_graph <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/wegner">Wegner</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>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a planar graph of maximum degree <img class="teximage" src="/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png" alt="$ \Delta $" />. The chromatic number of its square is<br /> <ul class="itemize"> \item at most <img class="teximage" src="/files/tex/daebc9d78b81a4cd1f0e6bae70785e92cf2ce1ea.png" alt="$ 7 $" /> if <img class="teximage" src="/files/tex/aced9ebeab44df5a1f3efd1bfb967dd0fe0883c4.png" alt="$ \Delta =3 $" />, \item at most <img class="teximage" src="/files/tex/a7be33e67abdf15a956bdc393747bb7f75bbd905.png" alt="$ \Delta+5 $" /> if <img class="teximage" src="/files/tex/edab53b759e15d01350d22f54590e6ee9a99bca9.png" alt="$ 4\leq\Delta\leq 7 $" />, \item at most <img class="teximage" src="/files/tex/d5aa6f60013e17601f35a898a36936e347bc9a8b.png" alt="$ \left\lfloor\frac32\,\Delta\right\rfloor+1 $" /> if <img class="teximage" src="/files/tex/0782472fc66f76ac853e14ef0f2ded9aaac96451.png" alt="$ \Delta\ge8 $" />. </ul> </div> </tr></td> </table> </td> </tr> </table> Wegner Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/colouring_the_square_of_a_planar_graph#comment Wed, 13 Mar 2013 09:47:52 +0100 fhavet 47470 at http://openproblemgarden.org