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

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

2003-06-10

arxiv.org/abs/math/0306158v1

Mathematics

Combinatorics

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-367970