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 perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs. © 2013 Elsevier B.V.

Registro:

Documento: Artículo
Título:Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey
Autor:Durán, G.
Filiación:Instituto de Cálculo and Departamento de Matemática, 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
CONICET, Argentina
Palabras clave:Balanced graphs; Clique graphs; Clique-perfect graphs; Coordinated graphs; K-perfect graphs; Perfect graphs
Año:2013
Volumen:44
Página de inicio:399
Página de fin:404
DOI: http://dx.doi.org/10.1016/j.endm.2013.10.062
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_v44_n_p399_Duran

Referencias:

  • Berge, C., Les problèmes de colorations en théorie des graphes (1960) Publications de l'Institut de Statistique de l'Université de Paris, 9, pp. 123-160
  • Berge, C., Färbung von Graphen, deren sämtliche beziehungsweise, deren ungerade Kreise starr sind (Zusammenfassung), Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg (1961) Mathematisch-Naturwissenschaftliche Reihe, 10, pp. 114-115
  • Berge, C., Balanced matrices (1972) Mathematical Programming, 2 (1), pp. 19-31
  • Berge, C., Chvátal, V., Introduction (1984) North-Holland Mathematics Studies, 88, pp. 7-15. , North-Holland, C. Berge, V. Chvátal (Eds.) Topics on Perfect Graphs
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs I: subclasses of claw-free graphs (2008) Disc. Applied Mathematics, 156 (7), pp. 1058-1082
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs II: diamond-free and Helly circular-arc graphs (2009) Discrete Mathematics, 309 (11), pp. 3485-3499
  • Bonomo, F., Durán, G., Groshaus, M., Coordinated graphs and clique graphs of clique-Helly perfect graphs (2007) Utilitas Mathematica, 72, pp. 175-191
  • Bonomo, F., Durán, G., Lin, M., Szwarcfiter, J., On Balanced Graphs (2006) Mathematical Programming. Series B, 105, pp. 233-250
  • Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., On minimal forbidden subgraph characterizations of balanced graphs (2009) Electronic Notes in Discrete Mathematics, 35, pp. 41-46
  • Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., Balancedness of some subclasses of circular-arc graphs (2010) Electronic Notes in Discrete Mathematics, 36, pp. 1121-1128
  • Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K., Clique-perfectness of complements of line graphs (2011) Electronic Notes in Discrete Mathematics, 37, pp. 327-332
  • Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs (2009) Disc. Applied Mathematics, 157 (17), pp. 3511-3518
  • Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of coordinated graphs: line graphs and complements of forests (2009) Mathematical Methods of Operations Research, 69 (2), pp. 251-270
  • Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vušković, K., Recognizing Berge Graphs (2005) Combinatorica, 25 (2), pp. 143-186
  • Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The Strong Perfect Graph Theorem (2006) Annals of Mathematics, 164 (1), pp. 51-229
  • Chvátal, V., On certain polytopes associated with graphs (1975) Journal of Combinatorial Theory. Series B, 18 (2), pp. 138-154
  • Dahlhaus, E., Manuel, P., Miller, M., Maximum h-colourable subgraph problem in balanced graphs (1998) Inform. Processing Letters, 65, pp. 301-303
  • 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., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Disc. Applied Mathematics, 100, pp. 183-202
  • Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discrete Mathematics, 61 (1), pp. 93-101
  • Lovász, L., A characterization of perfect graphs (1972) Journal of Combinatorial Theory. Series B, 13 (2), pp. 95-98
  • Soulignac, F., Sueiro, G., NP-hardness of the recognition of coordinated graphs (2009) Annals of Operations Research, 169 (1), pp. 17-34
  • Zambelli, G., A polynomial recognition algorithm for balanced matrices (2005) Journal of Combinatorial Theory. Series B, 95, pp. 49-67

Citas:

---------- APA ----------
(2013) . Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey. Electronic Notes in Discrete Mathematics, 44, 399-404.
http://dx.doi.org/10.1016/j.endm.2013.10.062
---------- CHICAGO ----------
Durán, G. "Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey" . Electronic Notes in Discrete Mathematics 44 (2013) : 399-404.
http://dx.doi.org/10.1016/j.endm.2013.10.062
---------- MLA ----------
Durán, G. "Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey" . Electronic Notes in Discrete Mathematics, vol. 44, 2013, pp. 399-404.
http://dx.doi.org/10.1016/j.endm.2013.10.062
---------- VANCOUVER ----------
Durán, G. Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey. Electron. Notes Discrete Math. 2013;44:399-404.
http://dx.doi.org/10.1016/j.endm.2013.10.062