Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
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 ve...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2008
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06073caa a22006377a 4500 | ||
|---|---|---|---|
| 001 | PAPER-6084 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203545.0 | ||
| 008 | 190411s2008 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-39349086272 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Bonomo, F. | |
| 245 | 1 | 0 | |a Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs |
| 260 | |c 2008 | ||
| 270 | 1 | 0 | |m Bonomo, F.; Departamento de Computaciíon, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina; email: fbonomo@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J., On clique-perfect and K-perfect graphs (2006) Ars Combin., 80, pp. 97-112 | ||
| 504 | |a 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 | ||
| 504 | |a Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The Strong Perfect Graph Theorem (2006) Ann. Math., 164, pp. 51-229 | ||
| 504 | |a Chvátal, V., Sbihi, N., Bull-free Berge graphs are perfect (1987) Graphs Combin., 3, pp. 127-139 | ||
| 504 | |a Durán, G., Lin, M., Szwarcfiter, J., On clique-transversal and cliqueindependent sets (2002) Ann. Oper. Res., 116, pp. 71-77 | ||
| 504 | |a Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl. Math., 100, pp. 183-202 | ||
| 504 | |a Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discrete Math., 61, pp. 93-101 | ||
| 504 | |a Maffray, F., Preissmann, M., On the NP-completeness of the k-colorability problem for triangle-free graphs (1996) Discrete Math., 162, pp. 313-317 | ||
| 504 | |a Nilli, A., Triangle-free graphs with large chromatic numbers (2000) Discrete Math., 211, pp. 261-262 | ||
| 504 | |a Olariu, S., Paw-free graphs (1988) Inf. Process. Lett., 28, pp. 53-54 | ||
| 504 | |a Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220 | ||
| 504 | |a Reed, B., Sbihi, N., Recognizing bull-free perfect graphs (1995) Graphs Combin., 11, pp. 171-178 | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq | ||
| 536 | |a Detalles de la financiación: Fondo Nacional de Desarrollo Científico, Tecnológico y de Innovación Tecnológica, 1050747 | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, X184 | ||
| 536 | |a Detalles de la financiación: 1 Partially supported by UBACyT Grant X184, Argentina and CNPq under PROSUL project Proc. 490333/2004-4, Brazil. 2Partially supported by FONDECyT Grant 1050747 and Millennium Science Institute “Complex Engineering Systems”, Chile and CNPq under PROSUL project Proc. 490333/2004-4, Brazil. 3 The work of this author has been supported by a grant of the YPF Foundation. | ||
| 593 | |a Departamento de Computaciíon, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Departamento de Ingeniería Industrial, FCFM, Universidad de Chile, Santiago, Chile | ||
| 593 | |a CONICET, Argentina | ||
| 690 | 1 | 0 | |a CLIQUE-PERFECT GRAPHS |
| 690 | 1 | 0 | |a COORDINATED GRAPHS |
| 690 | 1 | 0 | |a PAW-FREE GRAPHS |
| 690 | 1 | 0 | |a PERFECT GRAPHS |
| 690 | 1 | 0 | |a TRIANGLE-FREE GRAPHS |
| 690 | 1 | 0 | |a {GEM,W4,BULL}-FREE GRAPHS |
| 700 | 1 | |a Durán, G. | |
| 700 | 1 | |a Soulignac, F. | |
| 700 | 1 | |a Sueiro, G. | |
| 773 | 0 | |d 2008 |g v. 30 |h pp. 51-56 |k n. C |p Electron. Notes Discrete Math. |x 15710653 |t Electronic Notes in Discrete Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-39349086272&doi=10.1016%2fj.endm.2008.01.010&partnerID=40&md5=d353121ac28515984b250d1361ca1358 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.endm.2008.01.010 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p51_Bonomo |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p51_Bonomo |y Registro en la Biblioteca Digital |
| 961 | |a paper_15710653_v30_nC_p51_Bonomo |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 67037 | ||