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

Mostrar todas las versiones(2)

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Durán, Guillermo A., Soulignac, Francisco Juan
Publicado:	2009
Materias:	Clique-perfect graphs Coordinated graphs Paw-free graphs Perfect graphs Triangle-free graphs {gem, W4, bull}-free graphs {gem, W<sub>4</sub>, bull}-free graphs Gems Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v157_n17_p3511_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_0166218X_v157_n17_p3511_Bonomo
record_format	dspace
spelling	paper:paper_0166218X_v157_n17_p3511_Bonomo2023-06-08T15:15:28Z 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 Clique-perfect graphs Coordinated graphs Paw-free graphs Perfect graphs Triangle-free graphs {gem, W<sub>4</sub>, bull}-free graphs Gems Graph theory A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color 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 clique-perfect 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, both superclasses of triangle-free graphs. © 2009 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. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v157_n17_p3511_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_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 Clique-perfect graphs Coordinated graphs Paw-free graphs Perfect graphs Triangle-free graphs {gem, W<sub>4</sub>, bull}-free graphs Gems Graph theory
spellingShingle	Clique-perfect graphs Coordinated graphs Paw-free graphs Perfect graphs Triangle-free graphs {gem, W4, bull}-free graphs Clique-perfect graphs Coordinated graphs Paw-free graphs Perfect graphs Triangle-free graphs {gem, W<sub>4</sub>, bull}-free graphs Gems Graph theory 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 Clique-perfect graphs Coordinated graphs Paw-free graphs Perfect graphs Triangle-free graphs {gem, W<sub>4</sub>, bull}-free graphs Gems Graph theory
description	A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color 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 clique-perfect 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, both superclasses of triangle-free graphs. © 2009 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	2009
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v157_n17_p3511_Bonomo http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_Bonomo
work_keys_str_mv	AT bonomoflavia partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs AT duranguillermoa partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs AT soulignacfranciscojuan partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
_version_	1768545369073909760

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

Ejemplares similares