Combinatorics and Graph Theory


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: 77 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

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.

comments powered by Disqus