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

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

dc.contributor.author	Abu-Khzam, Faisal N.
dc.contributor.author	Feghali, Carl
dc.contributor.author	Muller, Haiko
dc.date.accessioned	2018-04-26T06:44:19Z
dc.date.available	2018-04-26T06:44:19Z
dc.date.copyright	2014	en_US
dc.date.issued	2018-04-26
dc.identifier.uri	http://hdl.handle.net/10725/7595
dc.description.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.	en_US
dc.language.iso	en	en_US
dc.title	NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph	en_US
dc.type	Article	en_US
dc.description.version	Pre-print	en_US
dc.author.school	SAS	en_US
dc.author.idnumber	200302941	en_US
dc.author.department	Computer Science and Mathematics	en_US
dc.description.embargo	N/A	en_US
dc.journal.volume	2	en_US
dc.journal.issue	1403.5248	en_US
dc.identifier.ctation	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.	en_US
dc.author.email	faisal.abukhzam@lau.edu.lb	en_US
dc.identifier.tou	http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php	en_US
dc.identifier.url	https://pdfs.semanticscholar.org/be27/7d8d21b644a768c443fe5553033ef879623f.pdf	en_US
dc.orcid.id	https://orcid.org/0000-0001-5221-8421	en_US
dc.author.affiliation	Lebanese American University	en_US