2014/03/24 by Abu-Khzam, Faisal N., Feghali, Carl, Müller, Haiko
#68R10 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1403.5961
A graph G = (V, E) is partitionable if there exists a partition \A, B\ of V such that A induces a disjoint union of cliques and B induces a triangle-free graph. In this paper we investigate the computational complexity of deciding whether a graph is partitionable. The problem is known to be \NP-complete on arbitrary graphs. Here it is proved that if a graph G is bull-free, planar, perfect, K4-free or does not contain certain holes then deciding whether G is partitionable is \NP-complete. This answers an open question posed by Thomassé, Trotignon and Vušković. In contrast a finite list of forbidden induced subgraphs is given for partitionable cographs.