http://openproblemgarden.org/op/bounding_the_chromatic_number_of_triangle_free_graphs_with_fixed_maximum_degree Comments for "Bounding the chromatic number of triangle-free graphs with fixed maximum degree" en http://openproblemgarden.org/op/bounding_the_chromatic_number_of_triangle_free_graphs_with_fixed_maximum_degree#comment-93641 <p>From Reed's conjecture, it seems that the ceiling has to be replaced by flooring. Thanks.</p> Sat, 16 May 2020 08:33:16 +0200 Anonymous comment 93641 at http://openproblemgarden.org http://openproblemgarden.org/op/bounding_the_chromatic_number_of_triangle_free_graphs_with_fixed_maximum_degree <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/kostochka_alexandr_v">Kostochka</a>; <a href="/category/reed_bruce_a">Reed</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; A triangle-free graph with maximum degree <img class="teximage" src="/files/tex/e3f8e135c571143e94f1d4f236326b862080b200.png" alt="$ \Delta $" /> has chromatic number at most <img class="teximage" src="/files/tex/522a3a86b51cce46cfcff77891e669d1b9ff9147.png" alt="$ \ceil{\frac{\Delta}{2}}+2 $" />.</p> </div> </tr></td> </table> </td> </tr> </table> Kostochka, Alexandr V. Reed, Bruce A. chromatic number girth maximum degree triangle free Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/bounding_the_chromatic_number_of_triangle_free_graphs_with_fixed_maximum_degree#comment Fri, 17 Apr 2009 14:37:46 +0200 Andrew King 36907 at http://openproblemgarden.org