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, F., Durán, G., Groshaus, M., Szwarcfiter, J.L.
Formato: JOUR
Materias:
Clique graphs
Clique-Helly graphs
Clique-perfect graphs
Good graphs
K-perfect graphs
Perfect graphs
Acceso en línea: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 todo:paper_03817032_v80_n_p97_Bonomo
record_format dspace
spelling todo:paper_03817032_v80_n_p97_Bonomo2023-10-03T15:33:42Z On clique-perfect and K-perfect graphs Bonomo, F. Durán, G. Groshaus, M. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, F.
Durán, G.
Groshaus, M.
Szwarcfiter, J.L.
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.
format JOUR
author Bonomo, F.
Durán, G.
Groshaus, M.
Szwarcfiter, J.L.
author_facet Bonomo, F.
Durán, G.
Groshaus, M.
Szwarcfiter, J.L.
author_sort Bonomo, F.
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
url http://hdl.handle.net/20.500.12110/paper_03817032_v80_n_p97_Bonomo
work_keys_str_mv AT bonomof oncliqueperfectandkperfectgraphs
AT durang oncliqueperfectandkperfectgraphs
AT groshausm oncliqueperfectandkperfectgraphs
AT szwarcfiterjl oncliqueperfectandkperfectgraphs
_version_ 1807318475721408512

Ejemplares similares