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 tC(G) and aC(G) the cardinalities of the minimum clique-transversal and maximum clique-independent set of G, respectively. Say that G is clique-perfect when tC(H)=aC(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 tC(G) and aC(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 tC(G)-aC(G) is arbitrarily large. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1023/A:1021363810398 | Annals OR |
Keywords | DocType | Volume |
clique-independent sets,clique-perfect graphs,clique-transversals,highly clique-imperfect graphs,integer linear programming,linear programming | Journal | 116 |
Issue | ISSN | Citations |
1-4 | 1572-9338 | 22 |
PageRank | References | Authors |
0.88 | 9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Guillermo Durán | 1 | 296 | 29.28 |
Min Chih Lin | 2 | 259 | 21.22 |
Jayme Luiz Szwarcfiter | 3 | 618 | 95.79 |