## On Retracts, Absolute Retracts, and Folds in Cographs

**Authors:** Ton Kloks, Yue-Li Wang

Let G and H be two cographs.
We show that the
problem to determine whether H is a retract of G
is NP-complete.
We show that this problem is fixed-parameter tractable when
parameterized by the size of H.
When restricted to the class of threshold graphs or
to the class of
trivially perfect graphs, the problem becomes tractable
in polynomial time. The problem is also
solvable in linear time
when one cograph is given as an induced subgraph
of the other. We characterize absolute retracts
for the class of cographs. Foldings generalize retractions.
We show that the problem to fold a
trivially perfect graph onto a largest possible clique is
NP-complete. For a threshold graph this folding number equals
its chromatic number and achromatic number.

**Comments:** 14 Pages.

**Download:** **PDF**

### Submission history

[v1] 2013-03-22 20:54:42

**Unique-IP document downloads:** 69 times

**Add your own feedback and questions here:**

*You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.*

*
*