OPEN
This is open, and cannot be resolved with a finite computation.
Let $\mathfrak{m}$ be an infinite cardinal and $G$ be a graph with chromatic number $\mathfrak{m}$. Let $r\geq 1$. Must $G$ contain a subgraph of chromatic number $\mathfrak{m}$ which does not contain any odd cycle of length $\leq r$?
A question of Erdős and Hajnal. Rödl proved this is true if $\mathfrak{m}=\aleph_0$ and $r=3$ (see
[108] for the finitary version).
More generally, Erdős and Hajnal asked must there exist (for every cardinal $\mathfrak{m}$ and integer $r$) some $f_r(\mathfrak{m})$ such that every graph with chromatic number $\geq f_r(\mathfrak{m})$ contains a subgraph with chromatic number $\mathfrak{m}$ with no odd cycle of length $\leq r$?
Erdős
[Er95d] claimed that even the $r=3$ case of this is open: must every graph with sufficiently large chromatic number contain a triangle free graph with chromatic number $\mathfrak{m}$?
In
[Er81] Erdős also asks the same question but with girth (i.e. the subgraph does not contain any cycle at all of length $\leq C$).
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #740, https://www.erdosproblems.com/740, accessed 2025-11-16
