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