Artículo
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 rc(G) and ac(G) the cardinalities of the minimum clique-ransversal 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.
Registro:
| Documento: | Artículo |
| Título: | On clique-transversals and clique-independent sets |
| Autor: | Durán, G.; Lin, M.C.; Szwarcfiter, J.L. |
| Filiación: | Departamento de Computación, Fac. de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina Instituto de Matemática, NCE and COPPE, Univ. Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil |
| Palabras clave: | Clique-independent sets; Clique-perfect graphs; Clique-transversals; Highly clique-imperfect graphs; Integer linear programming; Linear programming |
| Año: | 2002 |
| Volumen: | 116 |
| Número: | 1-4 |
| Página de inicio: | 71 |
| Página de fin: | 77 |
| DOI: | http://dx.doi.org/10.1023/A:1021363810398 |
| Título revista: | Annals of Operations Research |
| Título revista abreviado: | Ann. Oper. Res. |
| ISSN: | 02545330 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v116_n1-4_p71_Duran |
Referencias:
- Andreae, T., On the clique-transversal number of chordal graphs (1998) Discrete Mathematics, 191, pp. 3-11
- Andreae, T., Flotow, C., On covering all cliques of a chordal graph (1996) Discrete Mathematics, 149, pp. 299-302
- Andreae, T., Schughart, M., Tuza, Z., Clique-transversal sets of line graphs and complements of line graphs (1991) Discrete Mathematics, 88, pp. 11-20
- Balachandhran, V., Nagavamsi, P., Pandu Ragan, C., Clique transversal and clique independence on comparability graphs (1996) Information Processing Letters, 58, pp. 181-184
- Berge, C., Les problemes de colorations en théorie des graphes (1960) Publ. Inst. Stat. Univ. Paris, 9, pp. 123-160
- Chang, G., Farber, M., Tuza, Z., Algorithmic aspects of neighbourhood numbers (1993) SIAM Journal on Discrete Mathematics, 6, pp. 24-29
- Durán, G., (2000) Sobro Grafos Intersección de Arcos y Cuerdas en un Círculo, , Ph.D. Thesis, Universidad de Buenos Aires, Buenos Aires (in Spanish)
- Erdös, P., Gallai, T., Tuza, Z., Covering the cliques of a graph with vertices (1992) Discrete Mathematics, 108, pp. 279-289
- Fulkerson, D., Hoffman, A., Oppenheim, R., On balanced matrices (1974) Mathematical Programming, 1, pp. 120-132
- Golumbic, M., (1980) Algorithm Graph Theory and Perfect Graphs, , Academic Press, New York
- Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Applied Mathematics, 100, pp. 183-202
- Khachian, L., A polynomial algorithm in linear programming (1979) Soviet Math. Dokl., 20, pp. 191-194
- Lubiw, A., Short-chorded and perfect graphs (1991) Journal of Combinatorial Theory Series B, 51, pp. 24-33
- Prisner, E., Graphs with few cliques (1995) Graph Theory, Combinatorics and Applications: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications, pp. 945-956. , eds. Y. Alavi and A. Schwenk (Wiley, New York)
- Reed, B., (2000), Personal communication; Sun, L., Two classes of perfect graphs (1991) Journal of Combinatorial Theory Series B, 53, pp. 273-291
- Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, Y., A new algorithm for generating all the maximal independent sets (1977) SIAM Journal on Computing, 6, pp. 505-517
- Tuza, Z., Covering all cliques of a graph (1990) Discrete Mathematics, 86, pp. 117-126
Citas:
---------- APA ----------
Durán, G., Lin, M.C. & Szwarcfiter, J.L. (2002) . On clique-transversals and clique-independent sets. Annals of Operations Research, 116(1-4), 71-77.http://dx.doi.org/10.1023/A:1021363810398
---------- CHICAGO ----------
Durán, G., Lin, M.C., Szwarcfiter, J.L. "On clique-transversals and clique-independent sets" . Annals of Operations Research 116, no. 1-4 (2002) : 71-77.http://dx.doi.org/10.1023/A:1021363810398
---------- MLA ----------
Durán, G., Lin, M.C., Szwarcfiter, J.L. "On clique-transversals and clique-independent sets" . Annals of Operations Research, vol. 116, no. 1-4, 2002, pp. 71-77.http://dx.doi.org/10.1023/A:1021363810398
---------- VANCOUVER ----------
Durán, G., Lin, M.C., Szwarcfiter, J.L. On clique-transversals and clique-independent sets. Ann. Oper. Res. 2002;116(1-4):71-77.http://dx.doi.org/10.1023/A:1021363810398
