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

Summary: Can the vertices of an arbitrary 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-copmleteness of these problems are 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 if and only if \({\mathcal P}\)- and \({\mathcal Q}\)-recognition are both in NP. This completes the proof of a conjecture of \textit{J. Kratochvíl} and \textit{I. Schiermeyer} [Discuss. Math., Graph Theory 17, 253--258 (1997; Zbl 0904.05074)], various authors having already settled many subcases.