Brandstädt, Andreas; Esposito, Simone; Nogueira, Loana T.; Protti, Fábio Clique cycle-transversals in distance-hereditary graphs. (English) Zbl 1339.05084 Discrete Appl. Math. 210, 38-44 (2016). Summary: A cycle transversal or feedback vertex set of a graph \(G\) is a subset \(T \subseteq V(G)\) such that \(T \cap V(C) \neq \emptyset\) for every cycle \(C\) of \(G\). A clique cycle transversal, or cct for short, is a cycle transversal which is a clique. Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known. We characterize distance-hereditary graphs admitting a cct in terms of forbidden induced subgraphs. This extends similar results for chordal graphs and cographs. Cited in 1 Document MSC: 05C12 Distance in graphs 05C38 Paths and cycles Keywords:cycle transversal; distance-hereditary graphs; feedback vertex set; clique cycle transversal; forbidden induced subgraph characterization PDFBibTeX XMLCite \textit{A. Brandstädt} et al., Discrete Appl. Math. 210, 38--44 (2016; Zbl 1339.05084) Full Text: DOI arXiv References: [1] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory Ser. B, 41, 182-208 (1986) · Zbl 0605.05024 [2] Brandstädt, A., Partitions of graphs into one or two independent sets and cliques, Discrete Math., 152, 47-54 (1996) · Zbl 0853.68140 [3] Brandstädt, A., Corrigendum, Discrete Math., 186, 295 (1998) [4] Brandstädt, A.; Brito, S.; Klein, S.; Nogueira, L. T.; Protti, F., Cycle transversals in perfect graphs and cographs, Theoret. Comput. Sci., 469, 15-23 (2013) · Zbl 1259.68077 [5] Brandstädt, A.; Esposito, S.; Nogueira, L. T.; Protti, F., Clique cycle-transversals in distance-hereditary graphs (extended abstract), (Proc. of LAGOS 2013—VII Graphs, Algorithms, and Optimization Symposium. Proc. of LAGOS 2013—VII Graphs, Algorithms, and Optimization Symposium, Electronic Notes in Discrete Mathematics, vol. 44 (2013)), 15-21 [6] Brandstädt, A.; Le, V. B.; Spinrad, J. P., (Graph Classes: A Survey. Graph Classes: A Survey, SIAM Monographs on Discrete Math. Appl., vol. 3 (1999), SIAM: SIAM Philadelphia) · Zbl 0919.05001 [7] Bravo, R. S.F.; Nogueira, L. T.; Klein, S., Cographs \((k, l)\)-partitionable, (Proc. of the 7th International Colloquium on Graph Theory. Proc. of the 7th International Colloquium on Graph Theory, Electronic Notes in Discrete Mathematics, vol. 22 (2005)), 277-280 · Zbl 1200.05169 [8] Chvátal, V.; Hammer, P. L., Set-packing and threshold graphs. Res. Report CORR 73-21 (1973), University of Waterloo: University of Waterloo Ontario [9] Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 125-150 (2000) · Zbl 1009.68102 [11] Földes, S.; Hammer, P. L., Split graphs, Congr. Numer., 19, 311-315 (1977) [12] Groshaus, M.; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Cycle transversals in bounded degree graphs, Discrete Math. Theoret. Comput. Sci., 13, 45-66 (2011) · Zbl 1283.68155 [13] Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097 [14] Rao, M., MSOL partitioning problems on graphs of bounded treewidth and clique-width, Theoret. Comput. Sci., 377, 260-267 (2007) · Zbl 1118.68107 [15] Reed, B.; Smith, K.; Vetta, A., Finding odd cycle transversals, Oper. Res. Lett., 32, 299-301 (2004) · Zbl 1052.05061 [17] Zverovich, I. E.; Zverovich, I. I., An improvement of Gyárfás’ bounds on the maximal order of a minimal forbidden induced subgraph for \((1, 2)\)-split graphs. Research Report RRR 37-2002 (2002), RUTCOR This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.