On Clique-Transversals and Clique-Independent Sets |
| |
Authors: | Guillermo Durán Min Chih Lin Jayme L. Szwarcfiter |
| |
Affiliation: | (1) Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina;(2) Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil |
| |
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. |
| |
Keywords: | clique-independent sets clique-perfect graphs clique-transversals highly clique-imperfect graphs integer linear programming linear programming |
本文献已被 SpringerLink 等数据库收录! |
|