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, Nešetřil, and Rödl 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 (so Erdős writes, but I cannot find the reference).

See also [596].