Gyárfás–Sumner conjecture
For every tree T and every number t, can all graphs with no induced copy of T and no clique of t vertices be coloured with a number of colours that depends only on T and t?
Summary
András Gyárfás and David Sumner formulated the conjecture independently in 1975 and 1981. It says that excluding a tree as an induced subgraph keeps the chromatic number bounded in terms of the largest clique. It is proved for paths, stars and trees of radius two; graphs of large girth and chromatic number, found by Erdős and Hajnal, show that the tree cannot be replaced by a graph with cycles.
Source
Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 18 Nov 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.