Partitioning a graph into disjoint cliques and a triangle-free graph

Faisal Abu Khzam, C Feghali, H Muller

Research output: Contribution to journalArticle

1 Downloads (Pure)

Abstract

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 (i.e., G[A] is P3-free) and B induces a triangle-free graph (i.e., G[B] is K3-free). 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.
Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalDiscrete Applied Mathematics
Volume190-191
DOIs
Publication statusPublished - 20 Aug 2015
Externally publishedYes

Fingerprint Dive into the research topics of 'Partitioning a graph into disjoint cliques and a triangle-free graph'. Together they form a unique fingerprint.

Cite this