2003/06/10 by Alastair Farrugia, Farrugia, Alastair · 1 citation
Computer Science · Mathematics · #05C15 (Primary) 05C85 #68Q17 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C85 #msc:68Q17
paper · pdf · doi:10.48550/arxiv.math/0306158
10 pages, 1 figure, submitted to Electron. J. Combin
arxiv created 2003/06/10 · openalex publication_date 2003/06/10 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Can the vertices of a graph G be partitioned into A ∪ 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.