Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard

Abstract

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 $\mathcal{P}$ and $\mathcal{Q}$ are additive induced-hereditary graph properties, then $(\mathcal{P},\mathcal{Q})$-colouring is NP-hard, with the sole exception of graph 2-colouring (the case where both $\mathcal{P}$ and $\mathcal{Q}$ are the set $\mathcal{O}$ of finite edgeless graphs). Moreover, $(\mathcal{P},\mathcal{Q})$-colouring is NP-complete iff $\mathcal{P}$- and $\mathcal{Q}$-recognition are both in NP. This proves a conjecture of Kratochv\'ıl and Schiermeyer.

10 pages, 1 figure, submitted to Electron. J. Combin