Paper Info
Title
Clique cycle transversals in graphs with few P4's.
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 subset of V (G) such that T boolean AND V (C) not equal empty set 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.
Year
Venue
Keywords
2013
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
Clique,Cycle Transversal,Extended P-4-laden graph,Feedback Vertex Set
DocType
Volume
Issue
Journal
15.0
3.0
ISSN
Citations 
PageRank 
1462-7264
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Raquel S. F. Bravo151.13
Sulamita Klein230832.86
Loana Tito Nogueira316311.94
Fábio Protti435746.14