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

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Feghali, Carl
dc.contributor.author Muller, Haiko
dc.date.accessioned 2015-12-07T13:14:30Z
dc.date.available 2015-12-07T13:14:30Z
dc.date.copyright 2015
dc.date.issued 2015-12-07
dc.identifier.issn 0166-218X en_US
dc.identifier.uri http://hdl.handle.net/10725/2779
dc.description.abstract A graph G=(V,E) is partitionable if there exists a partition {A,B} of V such that A induces a disjoint union of cliques (i.e. , G[A] is P3-free) and B induces a triangle-free graph (i.e. , G[B] is K3-free). In this paper we investigate the computational complexity of deciding whether a graph is partitionable. The problem is known to be NP-complete on arbitrary graphs. Here it is proved that if a graph G is bull-free, planar, perfect, K4-free or does not contain certain holes then deciding whether G is partitionable is NP-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. en_US
dc.language.iso en en_US
dc.title Partitioning a graph into disjoint cliques and a triangle-free graph en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Discrete Applied Mathematics en_US
dc.journal.volume 190-191 en_US
dc.article.pages 1-12 en_US
dc.keywords Computational complexity en_US
dc.keywords Graph partitioning en_US
dc.keywords Special graph classes en_US
dc.identifier.doi http://dx.doi.org/10.1016/j.dam.2015.03.0151 en_US
dc.identifier.ctation Abu-Khzam, F. N., Feghali, C., & Müller, H. (2015). Partitioning a graph into disjoint cliques and a triangle-free graph. Discrete Applied Mathematics. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S0166218X1500164X
dc.orcid.id https://orcid.org/0000-0001-5221-8421

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account