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

2014/03/20 by Carl Feghali, Faisal N. Abu-Khzam, Feghali, Carl +3
Computer Science · Engineering · #68R10 #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1403.5248

openalex publication_date 2014/03/20 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

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

Related

• The complexity of partitioning into disjoint cliques and a triangle-free graph
• Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph
• Some NP-complete edge packing and partitioning problems in planar graphs
• Yet Another Graph Partitioning Problem is NP-Hard
• Four NP-complete problems about generalizations of perfect graphs