---
tag: 797WF2RPS5
kind: conjecture
name: Gyárfás–Sumner conjecture
sources:
  - wikipedia: en:56030165@r1375508681
    locator: Gyárfás–Sumner conjecture
    note: adopted
    mention: wikipedia://en/56030165
    sections: [Statement]
same_as:
  wikidata: Q48999679
  wikipedia: Gyárfás–Sumner conjecture
inventory: [22E1GBD24D]
---

## Statement

In graph theory, the **Gyárfás–Sumner conjecture** says that for any fixed [[tree|062D9KXJB1]] $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|0EREPBVG2G]] can be [[properly colored|0NCPXH194Y]] 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.