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

Marin Bougeret 1 Pascal Ochem 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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 cliques and a triangle-free graph is NP-complete for five graph classes. The problem is trivial for the intersection of these five classes. We prove that the problem is NP-complete for the intersection of two subsets of size four among the five classes. We also show NP-completeness for other small classes, such as graphs with maximum degree 4 and line graphs.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02078169
Contributor : Marin Bougeret <>
Submitted on : Monday, March 25, 2019 - 10:12:51 AM
Last modification on : Friday, May 3, 2019 - 12:08:04 PM

Links full text

Identifiers

Collections

Citation

Marin Bougeret, Pascal Ochem. The complexity of partitioning into disjoint cliques and a triangle-free graph. Discrete Applied Mathematics, Elsevier, 2017, 217, pp.438-445. ⟨10.1016/j.dam.2016.10.004⟩. ⟨lirmm-02078169⟩

Share

Metrics

Record views

39