Problem Statement
Is there some function $f$ such that for all $k\geq 3$ if a finite graph $G$ has chromatic number $\geq f(k)$ then $G$ must contain some odd cycle whose vertices span a graph of chromatic number $\geq k$?
Categories:
Graph Theory Chromatic Number
Progress
A problem of Erdős and Hajnal.Source: erdosproblems.com/640 | Last verified: January 15, 2026