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

Mostrar todas las versiones(4)

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, F., Durán, G., Soulignac, F., Sueiro, G.
Formato: Artículo publishedVersion
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:http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_Bonomo
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v157_n17_p3511_Bonomo_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_0166218X_v157_n17_p3511_Bonomo_oai
record_format dspace
spelling I28-R145-paper_0166218X_v157_n17_p3511_Bonomo_oai2024-08-16 Bonomo, F. Durán, G. Soulignac, F. Sueiro, G. 2009 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_Bonomo info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2009;157(17):3511-3518 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 Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v157_n17_p3511_Bonomo_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (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, F.
Durán, G.
Soulignac, F.
Sueiro, G.
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.
format Artículo
Artículo
publishedVersion
author Bonomo, F.
Durán, G.
Soulignac, F.
Sueiro, G.
author_facet Bonomo, F.
Durán, G.
Soulignac, F.
Sueiro, G.
author_sort Bonomo, F.
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 http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_Bonomo
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v157_n17_p3511_Bonomo_oai
work_keys_str_mv AT bonomof partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
AT durang partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
AT soulignacf partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
AT sueirog partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
_version_ 1809357215479365632

Ejemplares similares