Partial characterizations of clique-perfect graphs I: Subclasses of claw-free 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. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum cliqu...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Publicado: |
2008
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n7_p1058_Bonomo https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v156_n7_p1058_Bonomo_oai |
| Aporte de: |
| id |
I28-R145-paper_0166218X_v156_n7_p1058_Bonomo_oai |
|---|---|
| record_format |
dspace |
| spelling |
I28-R145-paper_0166218X_v156_n7_p1058_Bonomo_oai2024-08-16 Bonomo, F. Chudnovsky, M. Durán, G. 2008 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. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers 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. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n7_p1058_Bonomo info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2008;156(7):1058-1082 Claw-free graphs Clique-perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Image processing Mathematical models Number theory Problem solving Set theory Claw free graphs Clique perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Graph theory Partial characterizations of clique-perfect graphs I: Subclasses of claw-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_v156_n7_p1058_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 |
Claw-free graphs Clique-perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Image processing Mathematical models Number theory Problem solving Set theory Claw free graphs Clique perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Graph theory |
| spellingShingle |
Claw-free graphs Clique-perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Image processing Mathematical models Number theory Problem solving Set theory Claw free graphs Clique perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Graph theory Bonomo, F. Chudnovsky, M. Durán, G. Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs |
| topic_facet |
Claw-free graphs Clique-perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Image processing Mathematical models Number theory Problem solving Set theory Claw free graphs Clique perfect graphs Hereditary clique-Helly graphs Line graphs Perfect graphs 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. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers 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. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. © 2007 Elsevier B.V. All rights reserved. |
| format |
Artículo Artículo publishedVersion |
| author |
Bonomo, F. Chudnovsky, M. Durán, G. |
| author_facet |
Bonomo, F. Chudnovsky, M. Durán, G. |
| author_sort |
Bonomo, F. |
| title |
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs |
| title_short |
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs |
| title_full |
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs |
| title_fullStr |
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs |
| title_full_unstemmed |
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs |
| title_sort |
partial characterizations of clique-perfect graphs i: subclasses of claw-free graphs |
| publishDate |
2008 |
| url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v156_n7_p1058_Bonomo https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v156_n7_p1058_Bonomo_oai |
| work_keys_str_mv |
AT bonomof partialcharacterizationsofcliqueperfectgraphsisubclassesofclawfreegraphs AT chudnovskym partialcharacterizationsofcliqueperfectgraphsisubclassesofclawfreegraphs AT durang partialcharacterizationsofcliqueperfectgraphsisubclassesofclawfreegraphs |
| _version_ |
1809357090765930496 |