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].

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