Partitioning a graph into disjoint cliques and a triangle-free graph
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 part...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | article |
| Published: |
2015
|
| Online Access: | http://hdl.handle.net/10725/2779 http://dx.doi.org/10.1016/j.dam.2015.03.0151 http://www.sciencedirect.com/science/article/pii/S0166218X1500164X |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|