Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro 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. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers 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. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. © 2007 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
Autor:Bonomo, F.; Chudnovsky, M.; Durán, G.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Department of IEOR, Columbia University, New York, NY, United States
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
Palabras clave:Claw-free graphs; Clique-perfect graphs; Hereditary clique-Helly graphs; Line graphs; Perfect graphs; Image processing; Mathematical models; Number theory; Problem solving; Set theory; Claw free graphs; Clique perfect graphs; Hereditary clique-Helly graphs; Line graphs; Perfect graphs; Graph theory
Año:2008
Volumen:156
Número:7
Página de inicio:1058
Página de fin:1082
DOI: http://dx.doi.org/10.1016/j.dam.2007.05.048
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_v156_n7_p1058_Bonomo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v156_n7_p1058_Bonomo

Referencias:

  • Balachandhran, V., Nagavamsi, P., Pandu Rangan, C., Clique-transversal and clique-independence on comparability graphs (1996) Inform. Process. Lett., 58, pp. 181-184
  • Berge, C., (1985) Graphs and Hypergraphs, , North-Holland, Amsterdam
  • Berge, C., Las Vergnas, M., Sur un théorème du type König pour hypergraphes (1970) Ann. New York Acad. Sci., 175, pp. 32-40
  • 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., Durán, G., Lin, M., Szwarcfiter, J., On balanced graphs (2006) Math. Programming Ser. B, 105, pp. 233-250
  • Brandstädt, A., Chepoi, V., Dragan, F., Clique r-domination and clique r-packing problems on dually chordal graphs (1997) SIAM J. Discrete Math., 10, pp. 109-127
  • Chang, M., Farber, M., Tuza, Zs., Algorithmic aspects of neighbourhood numbers (1993) SIAM J. Discrete Math., 6, pp. 24-29
  • 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. of Math., 164, pp. 51-229
  • M. Chudnovsky, P. Seymour, Claw-free graphs. III. Circular interval graphs, submitted for publication; M. Chudnovsky, P. Seymour, Claw-free graphs. IV. Decomposition theorem, J. Combin. Theory Ser. B, to appear; Chvátal, V., Sbihi, N., Bull-free berge graphs are perfect (1987) Graphs Combin., 3, pp. 127-139
  • Conforti, M., Cornuéjols, G., Rao, R., Decomposition of balanced matrices (1999) J. Combin. Theory Ser. B, 77, pp. 292-406
  • Durán, G., Lin, M., Szwarcfiter, J., On clique-transversal and clique-independent sets (2002) Ann. Oper. Res., 116, pp. 71-77
  • Escalante, F., Über iterierte clique-graphen (1973) Abh. Math. Sem. Univ. Hamburg, 39, pp. 59-68
  • Golumbic, M., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, New York
  • 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) Discrete Appl. Math., 100, pp. 183-202
  • Lehel, J., Tuza, Zs., Neighborhood perfect graphs (1986) Discrete Math., 61, pp. 93-101
  • Lehot, P., An optimal algorithm to detect a line graph and output its root graph (1974) J. ACM, 21 (4), pp. 569-575
  • Maffray, F., Kernels in perfect line-graphs (1992) J. Combin. Theory Ser. B, 55, pp. 1-8
  • Maffray, F., Reed, B., A description of claw-free perfect graphs (1999) J. Combin. Theory Ser. B, 75 (1), pp. 134-156
  • Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220
  • Protti, F., Szwarcfiter, J., Clique-inverse graphs of bipartite graphs (2002) J. Combin. Math. Combin. Comput., 40, pp. 193-203
  • Rose, D., Tarjan, R., Lueker, G., Algorithmic aspects of vertex elimination on graphs (1976) SIAM J. Comput., 5, pp. 266-283
  • Trotter, L., Line perfect graphs (1977) Math. Programming, 12, pp. 255-259
  • Tucker, A., A reduction procedure for coloring perfect K4-free graphs (1987) J. Combin. Theory Ser. B, 43, pp. 151-172

Citas:

---------- APA ----------
Bonomo, F., Chudnovsky, M. & Durán, G. (2008) . Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs. Discrete Applied Mathematics, 156(7), 1058-1082.
http://dx.doi.org/10.1016/j.dam.2007.05.048
---------- CHICAGO ----------
Bonomo, F., Chudnovsky, M., Durán, G. "Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs" . Discrete Applied Mathematics 156, no. 7 (2008) : 1058-1082.
http://dx.doi.org/10.1016/j.dam.2007.05.048
---------- MLA ----------
Bonomo, F., Chudnovsky, M., Durán, G. "Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs" . Discrete Applied Mathematics, vol. 156, no. 7, 2008, pp. 1058-1082.
http://dx.doi.org/10.1016/j.dam.2007.05.048
---------- VANCOUVER ----------
Bonomo, F., Chudnovsky, M., Durán, G. Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs. Discrete Appl Math. 2008;156(7):1058-1082.
http://dx.doi.org/10.1016/j.dam.2007.05.048