Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

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

Abu-Khzam, Faisal N., Feghali, Carl and Muller, Haiko (2015). Partitioning a graph into disjoint cliques and a triangle-free graph. Discrete Applied Mathematics,190-191(20-Aug-15):1-12.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 83393865xPUB229
Title Partitioning a graph into disjoint cliques and a triangle-free graph
Author Abu-Khzam, Faisal N.
Feghali, Carl
Muller, Haiko
Journal Name Discrete Applied Mathematics
Publication Date 2015
Volume Number 190-191
Issue Number 20-Aug-15
ISSN 0166-218X   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84930479736
Start Page 1
End Page 12
Total Pages 12
Place of Publication Netherlands
Publisher Elsevier BV
Field of Research MATHEMATICAL SCIENCES
HERDC Category C1 - Journal Article (DIISR)
Abstract A graph G=(V,E)G=(V,E) is partitionable if there exists a partition {A,B}{A,B} of VV such that AA induces a disjoint union of cliques (i.e. , G[A]G[A] is P3P3-free) and BB induces a triangle-free graph (i.e. , G[B]G[B] is K3K3-free). In this paper we investigate the computational complexity of deciding whether a graph is partitionable. The problem is known to be NPNP-complete on arbitrary graphs. Here it is proved that if a graph GG is bull-free, planar, perfect, K4K4-free or does not contain certain holes then deciding whether GG is partitionable is NPNP-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.
Keywords Computational complexity
Graph partitioning
Special graph classes
DOI http://dx.doi.org/10.1016/j.dam.2015.03.015   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 163 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:40:42 CST