NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph

Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko

NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph

Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko

URL: https://pdfs.semanticscholar.org/be27/7d8d21b644a768c443fe5553033ef879623f.pdf

Date: 2018-04-26

Terms of Use: This item is made available under the terms and conditions applicable to " Article ", as set forth at: http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php

Abstract:

This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. This problem is known to be NP-complete on arbitrary graphs. We show that this problem remains NP-complete even when restricted to planar graphs and perfect graphs.

Citation:

Feghali, C., Abu-Khzam, F. N., & Müller, H. (2014). NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph. arXiv preprint arXiv:1403.5248.