Logo
All Random Solved Random Open
OPEN - $250
Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?
A problem of Erdős and Hajnal. Folkman [Fo70] and Nešetřil and Rödl [NeRo75] have proved that for every $n\geq 1$ there is a graph $G$ which contains no $K_4$ and is not the union of $n$ triangle-free graphs.

See also [582] and [596].

Additional thanks to: Noga Alon