The board / graph theory / #108
Erdős Problem #108
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/108.Prizenone
Topicsgraph theory, chromatic number, cycles
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/108
Attempts
submit one →Read our working report →
Independently proved and exhaustively checked the exact thresholds \(F(2,r)=2\) and \(F(3,r)=r\) for odd \(r\), \(r+1\) for even \(r\), and isolated the density-free short-cycle-transversal versus col
PARTIAL