Clique cycle-transversals in distance-hereditary graphs

被引：1

作者：

Brandstaedt, Andreas ^{[1
]}

Esposito, Simone ^{[2
]}

Nogueira, Loana T. ^{[2
]}

Protti, Fabio ^{[2
]}

机构：

[1] Univ Rostock, Inst Informat, D-18055 Rostock, Germany

[2] Univ Fed Fluminense, Inst Comp, Niteroi, RJ, Brazil

来源：

DISCRETE APPLIED MATHEMATICS | 2016年 / 210卷

关键词：

Cycle transversal; Distance-hereditary graphs; Feedback vertex set; Clique cycle transversal; Forbidden induced subgraph characterization; INDEPENDENT SETS; WIDTH;

D O I：

10.1016/j.dam.2014.12.007

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 0 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. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：38 / 44

页数：7

共 17 条

[1] DISTANCE-HEREDITARY GRAPHS [J].

BANDELT, HJ ;

MULDER, HM .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (02) :182-208

[2] Partitions of graphs into one or two independent sets and cliques (vol 152, pg 47, 1996) [J].

Brandstadt, A .

DISCRETE MATHEMATICS, 1998, 186 (1-3) :295-295

[3] Partitions of graphs into one or two independent sets and cliques [J].

Brandstadt, A .

DISCRETE MATHEMATICS, 1996, 152 (1-3) :47-54

[4]

Brandstadt A., 2013, ELECT NOTES DISCRETE, V44, P15

[5]

Brandstadt A., 1999, SIAM MONOGRAPHS DISC, V3

[6] Cycle transversals in perfect graphs and cographs [J].

Brandstaedt, Andreas ;

Brito, Synara ;

Klein, Sulamita ;

Nogueira, Loana Tito ;

Protti, Fabio .

THEORETICAL COMPUTER SCIENCE, 2013, 469 :15-23

[7]

Chvatal V, 1973, 7321 CORR U WAT

[8] Linear time solvable optimization problems on graphs of bounded clique-width [J].

Courcelle, B ;

Makowsky, JA ;

Rotics, U .

THEORY OF COMPUTING SYSTEMS, 2000, 33 (02) :125-150

[9]

de Souza-Francisco R., 2005, Electronic Notes in Discrete Mathematics, V22, P277

[10]

Feder T., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P464, DOI 10.1145/301250.301373

← 1 2 →