The complexity of partitioning into disjoint cliques and a triangle-free graph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Applied Mathematics Year : 2017

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

Marin Bougeret
Pascal Ochem

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.

Dates and versions

lirmm-02078169 , version 1 (25-03-2019)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More