On clique-transversals and clique-independent sets

On clique-transversals and clique-independent sets

0.00 Avg rating0 Votes
Article ID: iaor20031577
Country: Netherlands
Volume: 116
Issue: 1
Start Page Number: 71
End Page Number: 77
Publication Date: Oct 2002
Journal: Annals of Operations Research
Authors: , ,
Keywords: sets
Abstract:

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. A clique-independent set is a subset of pairwise disjoint cliques of G. Denote by τC(G) and αC(G) the cardinalities of the minimum clique-transversal and maximum clique-independent set of G, respectively. Say that G is clique-perfect when τC(H) = αC(H), for every induced subgraph H of G. In this paper, we prove that every graph not containing a 4-wheel nor a 3-fan as induced subgraphs and such that every odd cycle of length greater than 3 has a short chord is clique-perfect. The proof leads to polynomial time algorithms for finding the parameters τC(G) and αC(G), for graphs belonging to this class. In addition, we prove that to decide whether or not a given subset of vertices of a graph is a clique-transversal is Co-NP-Complete. The complexity of this problem has been mentioned as unknown in the literature. Finally, we describe a family of highly clique-imperfect graphs, that is, a family of graphs G whose difference τC(G)αC(G) is arbitrarily large.

Reviews

Required fields are marked *. Your email address will not be published.