pith. sign in

arxiv: 1302.1402 · v2 · pith:44JDK26Anew · submitted 2013-02-06 · 💻 cs.DM · math.CO

Clique cycle-transversals in distance-hereditary graphs

classification 💻 cs.DM math.CO
keywords graphscliquecycle-transversaldistance-hereditaryadmitadmittingcharacterizationcharacterize
0
0 comments X
read the original abstract

A cycle-transversal of a graph G is a subset T of V(G) such that T intersects every cycle 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.