Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. | Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard Alastair Farrugia afarrugia@ Malta Submitted Dec 19 2002 Accepted Jul 12 2004 Published Jul 19 2004 MR Subject Classifications 05C15 Primary 05C85 68Q17 Secondary Abstract Can the vertices of an arbitrary graph G be partitioned into A u 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 P and Q are additive induced-hereditary graph properties then P Q -colouring is NP-hard with the sole exception of graph 2-colouring the case where both P and Q are the set O of finite edgeless graphs . Moreover P Q -colouring is NP-complete iff P- and Q-recognition are both in NP. This completes the proof of a conjecture of Kratochvil and Schiermeyer various authors having already settled many sub-cases. Kratochvil and Schiermeyer conjectured in 19 that for any additive hereditary graph properties P and Q recognising graphs in P Q is NP-hard with the obvious exception of bipartite graphs the case where both P and Q are the set O of finite edgeless graphs . They settled the case where Q O and it was natural to extend the conjecture to induced-hereditary properties. Berger s result 3 that reducible additive induced-hereditary properties have infinitely many minimal forbidden subgraphs provided support for the extended conjecture. We prove the extension of the Kratochvil-Schiermeyer conjecture in this paper. Problems such as the following for an arbitrary graph G are therefore NP-complete. Can V G be partitioned into A u 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 For fixed k Ế m can G be partitioned into a k-degenerate subgraph a subgraph of maximum degree Ế and an m-edge-colourable subgraph Garey et al. 15 22 essentially showed O forests -colouring to be NP-complete while Brandstadt et .
