Gyárfás–Sumner conjecture

Template:Unsolved In graph theory, the Gyárfás–Sumner conjecture says that for any fixed pair of a tree $T$ and a complete graph $K_t$, every graph that is both $T$-free and $K_t$-free is also $\chi$-boundedTemplate:R; that is, every graph that contains neither $T$ nor $K_t$ as an induced subgraph can be properly colored using a constant number of colors. Equivalently, it says that every $K_t$-free graph $G$ contains any arbitrarily chosen tree $T$ (as an induced subgraph), as long as $\chi (G)$ is large enough. It is named after András Gyárfás and David Sumner, who formulated it independently in 1975 and 1981 respectively.Template:R It remains unproven.Template:R

In this conjecture, it is not possible to replace $T$ by a graph with cycles. As Paul Erdős and András Hajnal have shown, there exist graphs with arbitrarily large chromatic number and, at the same time, arbitrarily large girth.Template:R Using these graphs, one can obtain graphs that avoid any fixed choice of a cyclic graph and clique (of more than two vertices) as induced subgraphs, and exceed any fixed bound on the chromatic number.Template:R

The conjecture is known to be true for certain special choices of $T$, including paths,Template:R stars, and trees of radius two.Template:R It is also known that, for any tree $T$, the graphs that do not contain any subdivision of $T$ are $\chi$-bounded.Template:R

External links

• Graphs with a forbidden induced tree are chi-bounded, Open Problem Garden