Papex

Open problem · Mathematics · since 1975 · Open

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.

More in Mathematics