NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph
classification
💻 cs.DM
cs.CC
keywords
graphscliquescompletedisjointproblemsubgraphtriangle-freearbitrary
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{KYLJNUCD}
Prints a linked pith:KYLJNUCD badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.