Artículo
Bonomo, F.; Durán, G.; Groshaus, M.; Szwarcfiter, J.L. "On clique-perfect and K-perfect graphs" (2006) Ars Combinatoria. 80:97-112
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H is equal to the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. When equality holds for every clique subgraph of G, the graph is c-clique-perfect. A graph G is K-perfect when its clique graph K(G) is perfect. In this work, relations are described among the classes of perfect, K-perfect, clique-perfect and c-clique-perfect graphs. Besides, partial characterizations of K-perfect graphs using polyhedral theory and clique subgraphs are formulated.
Registro:
| Documento: | Artículo |
| Título: | On clique-perfect and K-perfect graphs |
| Autor: | Bonomo, F.; Durán, G.; Groshaus, M.; Szwarcfiter, J.L. |
| Filiación: | Dep. de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina Dep. de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile Instituto de Matemática, NCE, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil |
| Palabras clave: | Clique graphs; Clique-Helly graphs; Clique-perfect graphs; Good graphs; K-perfect graphs; Perfect graphs |
| Año: | 2006 |
| Volumen: | 80 |
| Página de inicio: | 97 |
| Página de fin: | 112 |
| Título revista: | Ars Combinatoria |
| Título revista abreviado: | Ars Comb. |
| ISSN: | 03817032 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo |
Referencias:
- Balachandhran, V., Nagavamsi, P., Rangan, C.P., Clique-transversal and clique-independence on comparability graphs (1996) Inf. Process. Lett., 58, pp. 181-184
- Berge, C., Les problèmes de colorations en théorie des graphes (1960) Publ. Inst. Stat. Univ. Paris, 9, pp. 123-160
- Berge, G., (1989) Hypergraphs, , North Holland
- Berge, C., Las Vergnas, M., Sur un théorème du type König pour hypergraphes (1970) Ann. N. Y. Acad. Sci., 175, pp. 32-40
- Bonomo, F., Durán, G., Groshaus, M., Coordinated graphs and clique graphs of clique-Helly perfect graphs Utilitas Mathematica, , to appear
- Bonomo, F., Durán, G., Lin, M., Szwarcfiter, J., On balanced graphs Mathematical Programming B, , to appear
- Brandstädt, A., Chepoi, V., Dragan, F., Clique r-domination and clique r-packing problems on dually chordal graphs (1997) SIAM J. Discrete Math., 10, pp. 109-127
- Brandstädt, A., Chepoi, V., Dragan, F., Voloshin, V., Dually chordal graphs (1998) SIAM J. Discrete Math., 11, pp. 437-455
- Chang, M., Farber, M., Tuza, Z., Algorithmic aspects of neighbourhood numbers (1993) SIAM J. Discrete Math., 6, pp. 24-29
- Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The strong perfect graph theorem Annals of Mathematics, , to appear
- Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vušković, K., Recognizing berge graphs (2005) Combinatorica, 25, pp. 143-187
- Chvátal, V., On certain polytopes associated with graphs (1975) J. Comb. Theory, Ser. B, 18, pp. 138-154
- Dahlhaus, E., Manuel, P., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inf. Process. Lett., 65, pp. 301-303
- Durán, G., Lin, M., Szwarcfiter, J., On clique-transversal and clique-independent sets (2002) Ann. Oper. Res., 116, pp. 71-77
- Escalante, F., Uber iterierte Clique-Graphen (1973) Abh. Math. Semin. Univ. Hamb., 39, pp. 59-68
- Golumbic, M., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, New York
- Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1, pp. 169-197
- Guruswami, V., Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl. Math., 100, pp. 183-202
- Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discrete Math., 61, pp. 93-101
- Lovász, L., A characterization of perfect graphs and the perfect graph conjecture (1972) J. Comb. Theory, Ser. B, 132, pp. 95-98
- Reed, B., personal communication; Szwarcfiter, J., Bornstein, C., Clique graphs of chordal and path graphs (1994) SIAM J. Discrete Math., 7, pp. 331-336
Citas:
---------- APA ----------
Bonomo, F., Durán, G., Groshaus, M. & Szwarcfiter, J.L. (2006) . On clique-perfect and K-perfect graphs. Ars Combinatoria, 80, 97-112.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo [ ]
---------- CHICAGO ----------
Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J.L. "On clique-perfect and K-perfect graphs" . Ars Combinatoria 80 (2006) : 97-112.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo [ ]
---------- MLA ----------
Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J.L. "On clique-perfect and K-perfect graphs" . Ars Combinatoria, vol. 80, 2006, pp. 97-112.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo [ ]
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J.L. On clique-perfect and K-perfect graphs. Ars Comb. 2006;80:97-112.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo [ ]
