Gyárfás–Sumner conjecture on chi-bounded forest-free graphs

From papers

Let TT be a forest, and let a graph be TT-free if it has no induced subgraph isomorphic to TT. A hereditary graph class is chi-bounded if there is a function f:NNf:\mathbb{N}\to\mathbb{N} such that every graph GG in the class and every induced subgraph HH of GG satisfy χ(H)f(ω(H))\chi(H)\leqslant f(\omega(H)), where χ(H)\chi(H) is the chromatic number and ω(H)\omega(H) is the clique number. Gyárfás–Sumner conjecture. For every forest TT, the class of TT-free graphs is chi-bounded. The conjecture was disproved by Briański, Davies, and Walczak, who constructed chi-bounded classes that are not polynomially chi-bounded.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yidong Zhou and Kaiyang Lan, “The optimal χ-bound for \P_6, dart, K_4\-free graphs”, arXiv:2607.14667 (2026).

Additional references

20 papers in this index state this conjecture (2018–2026). The statement above is taken from the most recent of them; the others are arXiv:2512.09176, arXiv:2512.04414, arXiv:2506.01070, arXiv:2506.23054, arXiv:2401.07776, arXiv:2310.04265, arXiv:2308.08768, arXiv:2308.05442, arXiv:2307.11946, arXiv:2212.02272, arXiv:2205.08291, arXiv:2202.13177, and 7 more.

Solutions 0

No solutions have been posted yet.