  Can the vertices of a graph $G$ be partitioned into $A \cup B$, so that
$G[A]$ is a line-graph and $G[B]$ is a forest? Can $G$ be partitioned into a
planar graph and a perfect graph? The NP-completeness of these problems are
just special cases of our result: if ${\cal P}$ and ${\cal Q}$ are additive
induced-hereditary graph properties, then $({\cal P}, {\cal Q})$-colouring is
NP-hard, with the sole exception of graph 2-colouring (the case where both
$\cal P$ and $\cal Q$ are the set ${\cal O}$ of finite edgeless graphs).
Moreover, $({\cal P}, {\cal Q})$-colouring is NP-complete iff ${\cal P}$- and
${\cal Q}$-recognition are both in NP. This proves a conjecture of
Kratochv\'{\i}l and Schiermeyer.
