Math Conjectures

Gyárfás–Sumner Conjecture

OPENLandmarkConjectureProposed 1975–1981 · Standard version

Canonical statement

For every finite tree TT and integer t≥2t\geq2, there is an integer c=c(T,t)c=c(T,t) such that every finite simple graph GG with chromatic number χ(G)>c\chi(G)>c and no clique on tt vertices contains an induced subgraph isomorphic to TT. Here χ(G)\chi(G) is the least number of colors in a proper vertex coloring, and an induced copy uses exactly the edges of GG between its chosen vertices.
View source LaTeX
For every finite tree \(T\) and integer \(t\geq2\),
there is an integer \(c=c(T,t)\) such that every finite simple graph
\(G\) with chromatic number \(\chi(G)>c\) and no clique on \(t\)
vertices contains an induced subgraph isomorphic to \(T\). Here
\(\chi(G)\) is the least number of colors in a proper vertex coloring,
and an induced copy uses exactly the edges of \(G\) between its chosen
vertices.
GRAPH-025:[Gyarfas1975RamseyCovering][Sumner1981Subtrees][NguyenScottSeymour2024]
Graph theoryCombinatorics

Notes

The conjecture is proved for numerous tree classes and graph classes, but no bound c(T,t)c(T,t) is known for arbitrary TT and tt.
The date range records the independent formulations by Gyárfás in 1975 and Sumner in 1981.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.