The Gyárfás-Sumner conjecture asserts that for each fixed tree , the class of graphs with
no induced subgraph isomorphic to
is a chi-bounded graph
class (Sumner 1981, Gyárfás 1987). Equivalently, for every positive
integer
there is a bound depending only on
and
on the chromatic number
of any such graph with clique
number at most
.
The conjecture holds when is a path graph, a star
graph, or a tree of graph
radius at most 2 (Scott and Seymour 2020). The conjecture
is equivalent to the corresponding statement for every forest,
since every forest is an induced
subgraph of a tree.