On clique-perfect and K-perfect graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H is equal to the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. When equality holds for every clique subgraph of G, the graph is c-clique-perfect. A graph G is K-perfect when...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, Flavia, Durán, Guillermo A., Groshaus, Marina E.
Publicado: 2006
Materias:
Clique graphs
Clique-Helly graphs
Clique-perfect graphs
Good graphs
K-perfect graphs
Perfect graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo
http://hdl.handle.net/20.500.12110/paper_03817032_v80_n_p97_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03817032_v80_n_p97_Bonomo
record_format dspace
spelling paper:paper_03817032_v80_n_p97_Bonomo2025-07-30T18:17:22Z On clique-perfect and K-perfect graphs Bonomo, Flavia Durán, Guillermo A. Groshaus, Marina E. Clique graphs Clique-Helly graphs Clique-perfect graphs Good graphs K-perfect graphs Perfect graphs A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H is equal to the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. When equality holds for every clique subgraph of G, the graph is c-clique-perfect. A graph G is K-perfect when its clique graph K(G) is perfect. In this work, relations are described among the classes of perfect, K-perfect, clique-perfect and c-clique-perfect graphs. Besides, partial characterizations of K-perfect graphs using polyhedral theory and clique subgraphs are formulated. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Groshaus, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo http://hdl.handle.net/20.500.12110/paper_03817032_v80_n_p97_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Clique graphs
Clique-Helly graphs
Clique-perfect graphs
Good graphs
K-perfect graphs
Perfect graphs
spellingShingle Clique graphs
Clique-Helly graphs
Clique-perfect graphs
Good graphs
K-perfect graphs
Perfect graphs
Bonomo, Flavia
Durán, Guillermo A.
Groshaus, Marina E.
On clique-perfect and K-perfect graphs
topic_facet Clique graphs
Clique-Helly graphs
Clique-perfect graphs
Good graphs
K-perfect graphs
Perfect graphs
description A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H is equal to the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. When equality holds for every clique subgraph of G, the graph is c-clique-perfect. A graph G is K-perfect when its clique graph K(G) is perfect. In this work, relations are described among the classes of perfect, K-perfect, clique-perfect and c-clique-perfect graphs. Besides, partial characterizations of K-perfect graphs using polyhedral theory and clique subgraphs are formulated.
author Bonomo, Flavia
Durán, Guillermo A.
Groshaus, Marina E.
author_facet Bonomo, Flavia
Durán, Guillermo A.
Groshaus, Marina E.
author_sort Bonomo, Flavia
title On clique-perfect and K-perfect graphs
title_short On clique-perfect and K-perfect graphs
title_full On clique-perfect and K-perfect graphs
title_fullStr On clique-perfect and K-perfect graphs
title_full_unstemmed On clique-perfect and K-perfect graphs
title_sort on clique-perfect and k-perfect graphs
publishDate 2006
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03817032_v80_n_p97_Bonomo
http://hdl.handle.net/20.500.12110/paper_03817032_v80_n_p97_Bonomo
work_keys_str_mv AT bonomoflavia oncliqueperfectandkperfectgraphs
AT duranguillermoa oncliqueperfectandkperfectgraphs
AT groshausmarinae oncliqueperfectandkperfectgraphs
_version_ 1840326932104740864

Ejemplares similares