### Clique cycle transversals in graphs with few P_{4}'s

*Raquel S. F. Bravo, Sulamita Klein, Loana T. Nogueira, Fábio Protti*

#### Abstract

A graph is extended P

_{4}-laden if each of its induced subgraphs with at most six vertices that contains more than two induced P_{4}'s is {2K_{2},C_{4}}-free. A cycle transversal (or feedback vertex set) of a graph G is a subset T ⊆V(G) such that T ∩V(C) ≠∅ for every cycle C of G; if, in addition, T is a clique, then T is a clique cycle transversal (cct). Finding a cct in a graph G is equivalent to partitioning V(G) into subsets C and F such that C induces a complete subgraph and F an acyclic subgraph. This work considers the problem of characterizing extended P_{4}-laden graphs admitting a cct. We characterize such graphs by means of a finite family of forbidden induced subgraphs, and present a linear-time algorithm to recognize them.Full Text: PDF PostScript