# zbMATH — the first resource for mathematics

Maximum clique transversals. (English) Zbl 1042.68619
Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 27th international workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42707-4). Lect. Notes Comput. Sci. 2204, 32-43 (2001).
Summary: A maximum clique transversal set in a graph $$G$$ is a set $$S$$ of vertices such that every maximum clique of $$G$$ contains at least a vertex in $$S$$. Clearly, removing a maximum clique transversal set reduces the clique number of a graph. We study algorithmic aspects of the problem, given a graph, to find a maximum clique transversal set of minimum cardinality. We consider the problem for planar graphs and present fixed parameter and approximation results.
We also examine some other graph classes: subclasses of chordal graphs such as $$k$$-trees, strongly chordal graphs, etc., graphs with few $$P_{4}$$s, comparability graphs, and distance hereditary graphs.
For the entire collection see [Zbl 0983.00052].
Reviewer: Reviewer (Berlin)

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: