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: JOUR
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
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_0166218X_v157_n17_p3511_Bonomo
record_format dspace
spelling todo:paper_0166218X_v157_n17_p3511_Bonomo2023-10-03T15:03:36Z Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs Bonomo, F. Durán, G. Soulignac, F. Sueiro, G. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, 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 JOUR
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
url http://hdl.handle.net/20.500.12110/paper_0166218X_v157_n17_p3511_Bonomo
work_keys_str_mv AT bonomof partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
AT durang partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
AT soulignacf partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
AT sueirog partialcharacterizationsofcliqueperfectandcoordinatedgraphssuperclassesoftrianglefreegraphs
_version_ 1807322461121806336

Ejemplares similares