http://openproblemgarden.org/op/chromatic_number_of_graphs_with_no_odd_hole Comments for "Bounding the chromatic number of graphs with no odd hole" en http://openproblemgarden.org/op/chromatic_number_of_graphs_with_no_odd_hole <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/gyarfas_andras">Gyarfas</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; There exists a fixed function <img class="teximage" src="/files/tex/e5839c90f2b5ca6fe2f58de668c9549b3ad831bd.png" alt="$ f : {\mathbb N} \rightarrow {\mathbb N} $" /> so that <img class="teximage" src="/files/tex/4ecaa216fb961541a2aa91c99df9d018ca9e5597.png" alt="$ \chi(G) \le f(\omega(G)) $" /> for every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> with no odd hole. </div> </tr></td> </table> </td> </tr> </table> Gyarfas, Andras chi-bounded coloring induced subgraph odd hole perfect graph Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/chromatic_number_of_graphs_with_no_odd_hole#comment Mon, 25 Jun 2007 00:17:23 +0200 mdevos 422 at http://openproblemgarden.org