Characterization and recognition of Helly circular-arc clique-perfect 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. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every i...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v22_n_p147_Bonomo |
| Aporte de: |
| id |
todo:paper_15710653_v22_n_p147_Bonomo |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_15710653_v22_n_p147_Bonomo2023-10-03T16:27:01Z Characterization and recognition of Helly circular-arc clique-perfect graphs Bonomo, F. Durán, G. Clique-perfect graphs Helly circular-arc graphs K-perfect graphs perfect 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. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set 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. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. In this work we characterize clique-perfect graphs by a restricted list of minimal forbidden induced subgraphs when the graph is a Helly circular-arc graph. This characterization leads to a polynomial time recognition algorithm for clique-perfect graphs inside this class of graphs. © 2005 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v22_n_p147_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 Helly circular-arc graphs K-perfect graphs perfect graphs |
| spellingShingle |
Clique-perfect graphs Helly circular-arc graphs K-perfect graphs perfect graphs Bonomo, F. Durán, G. Characterization and recognition of Helly circular-arc clique-perfect graphs |
| topic_facet |
Clique-perfect graphs Helly circular-arc graphs K-perfect graphs perfect graphs |
| 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. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set 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. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. In this work we characterize clique-perfect graphs by a restricted list of minimal forbidden induced subgraphs when the graph is a Helly circular-arc graph. This characterization leads to a polynomial time recognition algorithm for clique-perfect graphs inside this class of graphs. © 2005 Elsevier B.V. All rights reserved. |
| format |
JOUR |
| author |
Bonomo, F. Durán, G. |
| author_facet |
Bonomo, F. Durán, G. |
| author_sort |
Bonomo, F. |
| title |
Characterization and recognition of Helly circular-arc clique-perfect graphs |
| title_short |
Characterization and recognition of Helly circular-arc clique-perfect graphs |
| title_full |
Characterization and recognition of Helly circular-arc clique-perfect graphs |
| title_fullStr |
Characterization and recognition of Helly circular-arc clique-perfect graphs |
| title_full_unstemmed |
Characterization and recognition of Helly circular-arc clique-perfect graphs |
| title_sort |
characterization and recognition of helly circular-arc clique-perfect graphs |
| url |
http://hdl.handle.net/20.500.12110/paper_15710653_v22_n_p147_Bonomo |
| work_keys_str_mv |
AT bonomof characterizationandrecognitionofhellycirculararccliqueperfectgraphs AT durang characterizationandrecognitionofhellycirculararccliqueperfectgraphs |
| _version_ |
1807323312691347456 |