Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

Mostrar todas las versiones(2)

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Durán, Guillermo A., Soulignac, Francisco Juan
Publicado:	2008
Materias:	Clique-perfect graphs coordinated graphs paw-free graphs perfect graphs triangle-free graphs {gem,W4,bull}-free graphs
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p51_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p51_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_15710653_v30_nC_p51_Bonomo
record_format	dspace
spelling	paper:paper_15710653_v30_nC_p51_Bonomo2023-06-08T16:24:24Z Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs Bonomo, Flavia Durán, Guillermo A. Soulignac, Francisco Juan Clique-perfect graphs coordinated graphs paw-free graphs perfect graphs triangle-free graphs {gem,W4,bull}-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 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. 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:Soulignac, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2008 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p51_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p51_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 coordinated graphs paw-free graphs perfect graphs triangle-free graphs {gem,W4,bull}-free graphs
spellingShingle	Clique-perfect graphs coordinated graphs paw-free graphs perfect graphs triangle-free graphs {gem,W4,bull}-free graphs Bonomo, Flavia Durán, Guillermo A. Soulignac, Francisco Juan Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
topic_facet	Clique-perfect graphs coordinated graphs paw-free graphs perfect graphs triangle-free graphs {gem,W4,bull}-free graphs
description	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.
author	Bonomo, Flavia Durán, Guillermo A. Soulignac, Francisco Juan
author_facet	Bonomo, Flavia Durán, Guillermo A. Soulignac, Francisco Juan
author_sort	Bonomo, Flavia
title	Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
title_short	Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
title_full	Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
title_fullStr	Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
title_full_unstemmed	Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
title_sort	partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs
publishDate	2008
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p51_Bonomo http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p51_Bonomo
work_keys_str_mv	AT bonomoflavia partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs AT duranguillermoa partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs AT soulignacfranciscojuan partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
_version_	1768543867255128064

Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

Ejemplares similares