Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph

Faisal N. Abu-Khzam, Carl Feghali, Haiko Müller

A graph $G=(V,E)$ is \emph{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.…