Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
Journal
Discrete Applied Mathematics
Journal Volume
66
Journal Issue
3
Pages
189-203
Date Issued
1996
Author(s)
Abstract
Suppose G=(V,E) is a graph in which each maximal clique Ci is associated with an integer ri, where 0≤ri≤|Ci|. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that |D ∩ Ci|≥ri for every maximal clique Ci of G. The problem includes the clique-transversal problem, the i, 1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.
Type
journal article