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

Alastair Farrugia

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

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-completeness of these problems are 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 completes the proof of a conjecture of Kratochvíl and Schiermeyer, various authors having already settled many sub-cases.

Détail

DOI : 10.37236/1799

Classification : 05C15, 05C85, 68Q17
Mots-clés : vertex-partitioning, line-graph, planar graph, perfect graph, NP-hard