Problem 641

../

claims/: The 1 claim page of Problem 641, one per claimant's result; the problem's standing derives from them.

---

Statement. Is there some function $f$ such that for all $k\geq 1$ if a finite graph $G$ has chromatic number $\geq f(k)$ then $G$ has $k$ edge disjoint cycles on the same set of vertices?

Status. Disproved. The site labels the problem DISPROVED and credits the resolution to Janzer, Steiner and Sudakov [JSS24], noting that the statement fails already at $k=2$; the result is recorded as an accepted claim, on the refereed venue and the site's acceptance, on its claim page, from which the frontmatter standing is derived.

Source. erdosproblems.com/641, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #641, https://www.erdosproblems.com/641.

References.

• [JSS24] B. Janzer and R. Steiner and B. Sudakov, Chromatic number and regular subgraphs. arXiv:2410.02437 (2024); Bull. London Math. Soc. 58 (2026), no. 4, e70262, DOI.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• janzer_2025_chromatic_number_regular_subgraphs