Claims

../

1977_06_01_rodl: Rödl (Proc. Amer. Math. Soc., 1977) proves that for every k some f(k,4) exists: large chromatic number forces a triangle-free subgraph of chromatic number at least k, the r = 4 case of Problem 108 and the whole of Problem 923.

2026_08_03_steiner: Steiner (arXiv, 2026) proves that chromatic number at least exp(k^(3+o(1))) forces a triangle-free subgraph of chromatic number at least k, so f(k,4) is single-exponential, improving Rödl's tower bound; a preprint, not refereed.

2026_09_15_kohlmeyer_kruer: A kernel-checked Lean counterexample family certified by Conjectures.io in September 2026: finite graphs of arbitrarily large chromatic number whose four-cycle-free subgraphs are 6-colorable, so no f(7,5) exists.

2026_09_30_nguyen_walczak: Nguyen and Walczak's expository note of September 2026 explains the Kohlmeyer–Kruer construction and sharpens its bound from 6 to 3, refuting the question for every r at least 5 and k at least 4; not refereed.

---