Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
| dc.creator | Farrugia, Alastair | |
| dc.date | 2003-06-10 | |
| dc.date.accessioned | 2026-07-07T04:58:43Z | |
| dc.date.available | 2026-07-07T04:58:43Z | |
| dc.description | 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\'ıl and Schiermeyer. | |
| dc.description | 10 pages, 1 figure, submitted to Electron. J. Combin | |
| dc.identifier | https://arxiv.org/abs/math/0306158 | |
| dc.identifier | http://arxiv.org/abs/math/0306158 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67750 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 (Primary) 05C85, 68Q17 (Secondary) | |
| dc.title | Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard | |
| dc.type | text |