Logo
All Random Solved Random Open
OPEN
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$).