The complexity of partitioning into disjoint cliques and a triangle-free graph

Marin Bougeret, Pascal Ochem

Motivated by Chudnovsky's structure theorem of bull-free graphs, Abu-Khzam, Feghali, and Müller have recently proved that deciding if a graph has a vertex partition into disjoint c…