Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc (HCA) graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect HCA graphs. © 2007 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
Autor:Bonomo, F.; Chudnovsky, M.; Durán, G.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Department of IEOR, Department of Mathematics, Columbia University, New York, NY, United States
Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Clique-perfect graphs; Diamond-free graphs; Helly circular-arc graphs; K-perfect graphs; Perfect graphs; Claw-free graphs; Clique-perfect graphs; Forbidden induced subgraphs; Graph g; Helly circular-arc graphs; Independent sets; Induced subgraph; K-perfect graphs; Maximum cliques; New class; Partial characterizations; Perfect graphs; Polynomial-time; Recognition algorithms; Cavity resonators; Characterization; Diamonds; Polynomial approximation; Graph theory
Año:2009
Volumen:309
Número:11
Página de inicio:3485
Página de fin:3499
DOI: http://dx.doi.org/10.1016/j.disc.2007.12.054
Título revista:Discrete Mathematics
Título revista abreviado:Discrete Math
ISSN:0012365X
CODEN:DSMHA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v309_n11_p3485_Bonomo

Referencias:

  • Balachandhran, V., Nagavamsi, P., Pandu Rangan, C., Clique-transversal and clique-independence on comparability graphs (1996) Information Processing Letters, 58, pp. 181-184
  • Bandelt, H., Prisner, E., Clique graphs and Helly graphs (1991) Journal of Combinatorial Theory Series B, 51, pp. 34-45
  • Berge, C., Sur certains hypergraphes généralisant les graphes biparties (1970) Combinatorial Theory and Applications, pp. 119-133. , Erdo{double acute}s P., Rényi A., and Sós V. (Eds), North-Holland, Amsterdam
  • Berge, C., Las Vergnas, M., Sur un théorème du type König pour hypergraphes (1970) Annals of the New York Academy of Sciences, 175, pp. 32-40
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs (2005) Electronic Notes in Discrete Mathematics, 19, pp. 95-101
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs I: Sublcasses of claw-free graphs (2007) Discrete Applied Mathematics, , online, in press doi:10.1016/j.dam.2007.05.048, Available
  • Bonomo, F., Durán, G., Characterization and recognition of Helly circular-arc clique-perfect graphs (2005) Electronic Notes in Discrete Mathematics, 22, pp. 147-150
  • Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J., On clique-perfect and K-perfect graphs (2006) Ars Combinatoria, 80, pp. 97-112
  • Brandstädt, A., Chepoi, V., Dragan, F., Clique r-domination and clique r-packing problems on dually chordal graphs (1997) SIAM Journal on Discrete Mathematics, 10, pp. 109-127
  • Brandstädt, A., Le, V., Spinrad, J., (1999) Graph Classes: A Survey, , SIAM, Philadelphia
  • Chang, M., Farber, M., Tuza, Zs., Algorithmic aspects of neighbourhood numbers (1993) SIAM Journal on Discrete Mathematics, 6, pp. 24-29
  • Chong-Keang, L., Yee-Hock, P., On graphs without multicliqual edges (1981) Journal of Graph Theory, 5, pp. 443-451
  • Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vušković, K., Recognizing Berge graphs (2005) Combinatorica, 25, pp. 143-187
  • Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The strong perfect graph theorem (2006) Annals of Mathematics, 164, pp. 51-229
  • Conforti, M., Zambelli, G., Recognizing balanceable matrices (2006) Mathematical Programming Series B, 105, pp. 161-179
  • Durán, G., Lin, M., Mera, S., Szwarcfiter, J., Clique-independent sets on Helly circular-arc graphs (2004) Electronic Notes in Discrete Mathematics, 18, pp. 103-108
  • Durán, G., Lin, M., Mera, S., Szwarcfiter, J., Algorithms for finding clique-transversals of graphs (2008) Annals of Operations Research, 157, pp. 37-45
  • Durán, G., Lin, M., Szwarcfiter, J., On clique-transversal and clique-independent sets (2002) Annals of Operations Research, 116, pp. 71-77
  • Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
  • Golumbic, M., (2004) Annals of Discrete Mathematics, 57. , North-Holland, Amsterdam
  • Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Applied Mathematics, 100, pp. 183-202
  • Lee, C.M., Chang, M.S., Distance-hereditary graphs are clique-perfect (2006) Discrete Applied Mathematics, 154, pp. 525-536
  • Lehel, J., Tuza, Zs., Neighborhood perfect graphs (1986) Discrete Mathematics, 61, pp. 93-101
  • Lucchesi, C., Picinin de Mello, C., Szwarcfiter, J., On clique-complete graphs (1998) Discrete Mathematics, 183, pp. 247-254
  • Prisner, E., Hereditary clique-Helly graphs (1993) The Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 216-220
  • Wallis, W.D., Zhang, G.-H., On maximal clique irreducible graphs (1990) The Journal of Combinatorial Mathematics and Combinatorial Computing, 8, pp. 187-193
  • http://wwwteo.informatik.uni-rostock.de/isgci, Information system on graph class inclusions

Citas:

---------- APA ----------
Bonomo, F., Chudnovsky, M. & Durán, G. (2009) . Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs. Discrete Mathematics, 309(11), 3485-3499.
http://dx.doi.org/10.1016/j.disc.2007.12.054
---------- CHICAGO ----------
Bonomo, F., Chudnovsky, M., Durán, G. "Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs" . Discrete Mathematics 309, no. 11 (2009) : 3485-3499.
http://dx.doi.org/10.1016/j.disc.2007.12.054
---------- MLA ----------
Bonomo, F., Chudnovsky, M., Durán, G. "Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs" . Discrete Mathematics, vol. 309, no. 11, 2009, pp. 3485-3499.
http://dx.doi.org/10.1016/j.disc.2007.12.054
---------- VANCOUVER ----------
Bonomo, F., Chudnovsky, M., Durán, G. Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs. Discrete Math. 2009;309(11):3485-3499.
http://dx.doi.org/10.1016/j.disc.2007.12.054