Problem #641: Is there some function $f$ such that for all $k\geq 1$ if a...

---

Progress

A problem of Erdős and Hajnal.

This was resolved in the negative by Janzer, Steiner, and Sudakov [JSS24] - in fact, this fails even at $k=2$. Janzer, Steiner, and Sudakov proved that there exists a constant $c>0$ such that, for all large $n$, there exists a graph on $n$ vertices with chromatic number\[\geq c\frac{\log\log n}{\log\log \log n}\]which contains no $4$-regular subgraph.