/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
[Gy75] Gyárfás, A. (1975). "On Ramsey covering-numbers." Infinite and finite sets,
Colloq. Math. Soc. János Bolyai 10, pp. 801--816.
[Su81] Sumner, D. P. (1981). "Subtrees of a graph and the chromatic number." The theory
and applications of graphs (Kalamazoo, 1980), Wiley, pp. 557--576.
[Gy87] Gyárfás, A. (1987). "Problems from the world surrounding perfect graphs."
Zastos. Mat. 19, pp. 413--441.
[KP94] Kierstead, H. A. and Penrice, S. G. (1994). "Radius two trees specify χ-bounded
classes." J. Graph Theory 18, pp. 119--129.
[SS20] Scott, A. and Seymour, P. (2020). "A survey of χ-boundedness." J. Graph Theory 95,
pp. 473--504. arXiv:1812.07500
A class of graphs given by a forbidden induced subgraph T is χ-bounded by f if every
finite graph G with no induced copy of T satisfies χ(G) ≤ f(ω(G)).
The Gyárfás–Sumner conjecture (Gyárfás 1975, Sumner 1981).
For every finite tree $T$ the class of $T$-free graphs (graphs with no induced subgraph
isomorphic to $T$) is $\chi$-bounded: there is a function $f$ such that every $T$-free graph
$G$ satisfies $\chi(G) \le f(\omega(G))$.
For every $n$, the class of $P_n$-free graphs is $\chi$-bounded. For $n \ge 2$ and
nonempty $G$, Gyárfás's argument gives $\chi(G) \le (n-1)^{\omega(G) - 1}$.
The conjecture is trivial when T is a single vertex.
If $T$ is a single vertex then every nonempty graph contains an induced copy of $T$, so the
only $T$-free graph is the empty graph, whose chromatic number is $0$; hence
$f = 0$ works.