Problem 641

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?

Source: erdosproblems.com/641

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

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 (Janzer Steiner Sudakov, 2024), from which the frontmatter standing is derived.

Problem 641

Status

Proof claims

Discussion