NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph
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 rest...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | article |
| Published: |
2014
|
| Online Access: | http://hdl.handle.net/10725/7595 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://pdfs.semanticscholar.org/be27/7d8d21b644a768c443fe5553033ef879623f.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|