Nemotron-IMO-Bench 2026 C35

A graph $G$ contains no $K_4$ and its chromatic number is $\geq 4$. Prove that there is a partition $V(G)=A\cup B$ such that the graphs induced by $A$ and $B$ have chromatic numbers $\geq 3$ and $\geq 2$.