Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs

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. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every i...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Durán, Guillermo A.
Publicado:	2009
Materias:	Clique-perfect graphs Diamond-free graphs Helly circular-arc graphs K-perfect graphs Perfect graphs Claw-free graphs Forbidden induced subgraphs Graph g Independent sets Induced subgraph Maximum cliques New class Partial characterizations Polynomial-time Recognition algorithms Cavity resonators Characterization Diamonds Polynomial approximation Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v309_n11_p3485_Bonomo http://hdl.handle.net/20.500.12110/paper_0012365X_v309_n11_p3485_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_0012365X_v309_n11_p3485_Bonomo
record_format	dspace
spelling	paper:paper_0012365X_v309_n11_p3485_Bonomo2023-06-08T14:35:22Z Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs Bonomo, Flavia Durán, Guillermo A. Clique-perfect graphs Diamond-free graphs Helly circular-arc graphs K-perfect graphs Perfect graphs Claw-free graphs Clique-perfect graphs Forbidden induced subgraphs Graph g Helly circular-arc graphs Independent sets Induced subgraph K-perfect graphs Maximum cliques New class Partial characterizations Perfect graphs Polynomial-time Recognition algorithms Cavity resonators Characterization Diamonds Polynomial approximation Graph theory 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. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set 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. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc (HCA) graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect HCA graphs. © 2007 Elsevier B.V. All rights reserved. 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. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v309_n11_p3485_Bonomo http://hdl.handle.net/20.500.12110/paper_0012365X_v309_n11_p3485_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-perfect graphs Diamond-free graphs Helly circular-arc graphs K-perfect graphs Perfect graphs Claw-free graphs Clique-perfect graphs Forbidden induced subgraphs Graph g Helly circular-arc graphs Independent sets Induced subgraph K-perfect graphs Maximum cliques New class Partial characterizations Perfect graphs Polynomial-time Recognition algorithms Cavity resonators Characterization Diamonds Polynomial approximation Graph theory
spellingShingle	Clique-perfect graphs Diamond-free graphs Helly circular-arc graphs K-perfect graphs Perfect graphs Claw-free graphs Clique-perfect graphs Forbidden induced subgraphs Graph g Helly circular-arc graphs Independent sets Induced subgraph K-perfect graphs Maximum cliques New class Partial characterizations Perfect graphs Polynomial-time Recognition algorithms Cavity resonators Characterization Diamonds Polynomial approximation Graph theory Bonomo, Flavia Durán, Guillermo A. Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
topic_facet	Clique-perfect graphs Diamond-free graphs Helly circular-arc graphs K-perfect graphs Perfect graphs Claw-free graphs Clique-perfect graphs Forbidden induced subgraphs Graph g Helly circular-arc graphs Independent sets Induced subgraph K-perfect graphs Maximum cliques New class Partial characterizations Perfect graphs Polynomial-time Recognition algorithms Cavity resonators Characterization Diamonds Polynomial approximation Graph theory
description	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. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set 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. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc (HCA) graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect HCA graphs. © 2007 Elsevier B.V. All rights reserved.
author	Bonomo, Flavia Durán, Guillermo A.
author_facet	Bonomo, Flavia Durán, Guillermo A.
author_sort	Bonomo, Flavia
title	Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
title_short	Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
title_full	Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
title_fullStr	Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
title_full_unstemmed	Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
title_sort	partial characterizations of clique-perfect graphs ii: diamond-free and helly circular-arc graphs
publishDate	2009
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0012365X_v309_n11_p3485_Bonomo http://hdl.handle.net/20.500.12110/paper_0012365X_v309_n11_p3485_Bonomo
work_keys_str_mv	AT bonomoflavia partialcharacterizationsofcliqueperfectgraphsiidiamondfreeandhellycirculararcgraphs AT duranguillermoa partialcharacterizationsofcliqueperfectgraphsiidiamondfreeandhellycirculararcgraphs
_version_	1768544484806623232

Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs

Ejemplares similares