×

Clique cycle-transversals in distance-hereditary graphs. (English) Zbl 1339.05084

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.

MSC:

05C12 Distance in graphs
05C38 Paths and cycles
PDFBibTeX XMLCite
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.