Gyárfás–Sumner conjecture

Statement

In graph theory, the Gyárfás–Sumner conjecture says that for any fixed tree $T$, the class of all $T$-free graphs is $\chi$-bounded; 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, depending only on $T$ and $t$. 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. It remains unproven.