Artículo
Abstract:
A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. In this work we characterize clique-perfect graphs by a restricted list of minimal forbidden induced subgraphs when the graph is a Helly circular-arc graph. This characterization leads to a polynomial time recognition algorithm for clique-perfect graphs inside this class of graphs. © 2005 Elsevier B.V. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | Characterization and recognition of Helly circular-arc clique-perfect graphs |
| Autor: | Bonomo, F.; Durán, G. |
| Filiación: | Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile |
| Palabras clave: | Clique-perfect graphs; Helly circular-arc graphs; K-perfect graphs; perfect graphs |
| Año: | 2005 |
| Volumen: | 22 |
| Página de inicio: | 147 |
| Página de fin: | 150 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2005.06.026 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v22_n_p147_Bonomo |
Referencias:
- Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs (2005) Electron. Notes Discrete Math., 19, pp. 95-101
- Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vušković, K., Recognizing Berge Graphs (2005) Combinatorica, 25, pp. 143-187
- Durán, G., Lin, M., Mera, S., Szwarcfiter, J., Clique-independent sets on Helly circular-arc graphs (2004) Electron. Notes Discrete Math., 18, pp. 103-108
- Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
- Guruswami, V., Pandu Rangan, C., 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
- Lucchesi, C., Picinin de Mello, C., Szwarcfiter, J., On clique-complete graphs (1998) Discrete Math., 183, pp. 247-254
Citas:
---------- APA ----------
Bonomo, F. & Durán, G. (2005) . Characterization and recognition of Helly circular-arc clique-perfect graphs. Electronic Notes in Discrete Mathematics, 22, 147-150.http://dx.doi.org/10.1016/j.endm.2005.06.026
---------- CHICAGO ----------
Bonomo, F., Durán, G. "Characterization and recognition of Helly circular-arc clique-perfect graphs" . Electronic Notes in Discrete Mathematics 22 (2005) : 147-150.http://dx.doi.org/10.1016/j.endm.2005.06.026
---------- MLA ----------
Bonomo, F., Durán, G. "Characterization and recognition of Helly circular-arc clique-perfect graphs" . Electronic Notes in Discrete Mathematics, vol. 22, 2005, pp. 147-150.http://dx.doi.org/10.1016/j.endm.2005.06.026
---------- VANCOUVER ----------
Bonomo, F., Durán, G. Characterization and recognition of Helly circular-arc clique-perfect graphs. Electron. Notes Discrete Math. 2005;22:147-150.http://dx.doi.org/10.1016/j.endm.2005.06.026
