Artículo

Artículo de Acceso Abierto. Puede ser descargado en su versión final
Consulte el artículo en la página del editor
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 equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color 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 clique-perfect 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, both superclasses of triangle-free graphs. © 2009 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ón, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
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:Clique-perfect graphs; Coordinated graphs; Paw-free graphs; Perfect graphs; Triangle-free graphs; {gem, W4, bull}-free graphs; Clique-perfect graphs; Coordinated graphs; Paw-free graphs; Perfect graphs; Triangle-free graphs; {gem, W4, bull}-free graphs; Gems; Graph theory
Año:2009
Volumen:157
Número:17
Página de inicio:3511
Página de fin:3518
DOI: http://dx.doi.org/10.1016/j.dam.2009.03.017
Handle:http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_Bonomo
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v157_n17_p3511_Bonomo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v157_n17_p3511_Bonomo

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
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs (2008) Discrete 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 Discrete Mathematics, , in press doi:10.1016/j.disc.2007.12.054
  • 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., 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
  • Durán, G., Lin, M., Szwarcfiter, J., On clique-transversal and clique-independent sets (2002) Annals of Operations Research, 116 (1), pp. 71-77
  • 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 (3), pp. 183-202
  • Hayward, R., Bull-free weakly chordal perfectly orderable graphs (2001) Graphs and Combinatorics, 17, pp. 479-500
  • Jin, G., Triangle-free four-chromatic graphs (1995) Discrete Mathematics, 145, pp. 151-170
  • Konig, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre (1916) Mathematische Annalen, 77, pp. 453-465
  • Konig, D., Graphok és Matrixok (1931) Matematikai és Fizikai Lapok, 38, pp. 116-119
  • Lee, C.M., Chang, M.S., Distance-hereditary graphs are clique-perfect (2006) Discrete Applied Mathematics, 154 (3), pp. 525-536
  • Lehel, J., Tuza, Zs., 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
  • Maffray, F., Preissmann, M., On the NP-completeness of the k-colorability problem for triangle-free graphs (1996) Discrete Mathematics, 162, pp. 313-317
  • Nilli, A., Triangle-free graphs with large chromatic numbers (2000) Discrete Mathematics, 211 (1-3), pp. 261-262
  • Olariu, S., Paw-free graphs (1988) Information Processing Letters, 28, pp. 53-54
  • Prisner, E., Hereditary clique-Helly graphs (1993) The Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 216-220
  • Reed, B., Sbihi, N., Recognizing bull-free perfect graphs (1995) Graphs and Combinatorics, 11 (4), pp. 171-178
  • Soulignac, F., Sueiro, G., NP-hardness of the recognition of coordinated graphs (2009) Annals of Operations Research, 169 (1), pp. 17-34
  • Soulignac, F., Sueiro, G., (2006) Exponential Families of minimally non-coordinated graphs, , submitted for publication

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Soulignac, F. & Sueiro, G. (2009) . Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs. Discrete Applied Mathematics, 157(17), 3511-3518.
http://dx.doi.org/10.1016/j.dam.2009.03.017
---------- CHICAGO ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. "Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs" . Discrete Applied Mathematics 157, no. 17 (2009) : 3511-3518.
http://dx.doi.org/10.1016/j.dam.2009.03.017
---------- MLA ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. "Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs" . Discrete Applied Mathematics, vol. 157, no. 17, 2009, pp. 3511-3518.
http://dx.doi.org/10.1016/j.dam.2009.03.017
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs. Discrete Appl Math. 2009;157(17):3511-3518.
http://dx.doi.org/10.1016/j.dam.2009.03.017