Open Problem Garden - Graphs with a forbidden induced tree are chi-bounded - Comments http://openproblemgarden.org/op/graphs_with_a_forbidden_induced_tree_are_chi_bounded Comments for "Graphs with a forbidden induced tree are chi-bounded" en Graphs with a forbidden induced tree are chi-bounded http://openproblemgarden.org/op/graphs_with_a_forbidden_induced_tree_are_chi_bounded <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> <p>Say that a family <img class="teximage" src="/files/tex/a800ea52e334839ea4040a7939b0d8e9a32eefd5.png" alt="$ {\mathcal F} $" /> of graphs is <img class="teximage" src="/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png" alt="$ \chi $" />-<em>bounded</em> if there exists a function <img class="teximage" src="/files/tex/0c21c02685676711acbd250ed6ea0e83cdf80e5f.png" alt="$ f: {\mathbb N} \rightarrow {\mathbb N} $" /> so that every <img class="teximage" src="/files/tex/9506fcc7ba88f6eb3392967e31911b49d5afba61.png" alt="$ G \in {\mathcal F} $" /> satisfies <img class="teximage" src="/files/tex/6b22ddc229e21d77a9f6d7b9fefe88c2627a46f0.png" alt="$ \chi(G) \le f (\omega(G)) $" />. </p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For every fixed tree <img class="teximage" src="/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png" alt="$ T $" />, the family of graphs with no induced subgraph isomorphic to <img class="teximage" src="/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png" alt="$ T $" /> is <img class="teximage" src="/files/tex/0308ad82f7a52e8b5406c475bffba60ea6867b7a.png" alt="$ \chi $" />-bounded. </div> </tr></td> </table> </td> </tr> </table> Gyarfas, Andras chi-bounded coloring excluded subgraph tree Graph Theory Coloring Vertex coloring http://openproblemgarden.org/op/graphs_with_a_forbidden_induced_tree_are_chi_bounded#comment Sat, 16 May 2009 17:57:56 +0200 mdevos 36936 at http://openproblemgarden.org