Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A graph is clique-perfect if the cardinality of a maximum clique-independent set equals the cardinality of a minimum clique-transversal, for all its induced subgraphs. A graph G is coordinated if the chromatic number of the clique graph of H equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of cliqueperfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem,W4,bull}-free, two superclasses of triangle-free graphs. © 2008 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
Autor:Bonomo, F.; Durán, G.; Soulignac, F.; Sueiro, G.
Filiación:Departamento de Computaciíon, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile
CONICET, Argentina
Palabras clave:Clique-perfect graphs; coordinated graphs; paw-free graphs; perfect graphs; triangle-free graphs; {gem,W4,bull}-free graphs
Año:2008
Volumen:30
Número:C
Página de inicio:51
Página de fin:56
DOI: http://dx.doi.org/10.1016/j.endm.2008.01.010
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_v30_nC_p51_Bonomo

Referencias:

  • Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of cliqueperfect graphs I: sublcasses of claw-free graphs, Discrete Appl. Math. (2007), to appear; Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of cliqueperfect graphs II: diamond-free and Helly circular-arc graphs (2005), submitted; Bonomo, F., Durán, G., Groshaus, M., Coordinated graphs and clique graphs of clique-Helly perfect graphs (2007) Util. Math., 72, pp. 175-191
  • Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J., On clique-perfect and K-perfect graphs (2006) Ars Combin., 80, pp. 97-112
  • Bonomo, F., G. Durán, F. Soulignac and G. Sueiro, Partial characterizations of coordinated graphs: line graphs and complements of forests (2006), submitted; 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) Ann. Math., 164, pp. 51-229
  • Chvátal, V., Sbihi, N., Bull-free Berge graphs are perfect (1987) Graphs Combin., 3, pp. 127-139
  • Durán, G., Lin, M., Szwarcfiter, J., On clique-transversal and cliqueindependent sets (2002) Ann. Oper. Res., 116, pp. 71-77
  • 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
  • Maffray, F., Preissmann, M., On the NP-completeness of the k-colorability problem for triangle-free graphs (1996) Discrete Math., 162, pp. 313-317
  • Nilli, A., Triangle-free graphs with large chromatic numbers (2000) Discrete Math., 211, pp. 261-262
  • Olariu, S., Paw-free graphs (1988) Inf. Process. Lett., 28, pp. 53-54
  • Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220
  • Reed, B., Sbihi, N., Recognizing bull-free perfect graphs (1995) Graphs Combin., 11, pp. 171-178
  • Soulignac, F. and G. Sueiro, Exponential families of minimally non-coordinated graphs (2006), submitted; Soulignac, F. and G. Sueiro, NP-hardness of the recognition of coordinated graphs, in: Ann. XIII CLAIO, Montevideo, Uruguay, 2006

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Soulignac, F. & Sueiro, G. (2008) . Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs. Electronic Notes in Discrete Mathematics, 30(C), 51-56.
http://dx.doi.org/10.1016/j.endm.2008.01.010
---------- CHICAGO ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. "Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs" . Electronic Notes in Discrete Mathematics 30, no. C (2008) : 51-56.
http://dx.doi.org/10.1016/j.endm.2008.01.010
---------- MLA ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. "Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs" . Electronic Notes in Discrete Mathematics, vol. 30, no. C, 2008, pp. 51-56.
http://dx.doi.org/10.1016/j.endm.2008.01.010
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs. Electron. Notes Discrete Math. 2008;30(C):51-56.
http://dx.doi.org/10.1016/j.endm.2008.01.010