http://openproblemgarden.org/op/2_colouring_a_graph_without_a_monochromatic_maximum_clique Comments for "2-colouring a graph without a monochromatic maximum clique" en http://openproblemgarden.org/op/2_colouring_a_graph_without_a_monochromatic_maximum_clique <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/hoang">Hoang</a>; <a href="/category/mcdiarmid_colin">McDiarmid</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; If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a non-empty graph containing no induced odd cycle of length at least <img class="teximage" src="/files/tex/87f5fe1d4b06035debb52cf2d67802fbfa9cb4ab.png" alt="$ 5 $" />, then there is a <img class="teximage" src="/files/tex/5271e36bb1c040e0f14061d89cd97d0c86d4e06f.png" alt="$ 2 $" />-vertex colouring of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> in which no maximum clique is monochromatic. </div> </tr></td> </table> </td> </tr> </table> Hoang, Chinh T. McDiarmid, Colin maximum clique Partitioning Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/2_colouring_a_graph_without_a_monochromatic_maximum_clique#comment Sun, 25 Aug 2013 20:41:15 +0200 Jon Noel 56230 at http://openproblemgarden.org