Clique cycle transversals in graphs with few P4's
Raquel S. F. Bravo, Sulamita Klein, Loana T. Nogueira, Fábio Protti
Abstract
A graph is extended P4-laden if each of its
induced subgraphs with at most six vertices that contains more than
two induced P4's is
{2K2,C4}-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 P4-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