Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey
A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes rel...
| Autor principal: | |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v44_n_p399_Duran |
| Aporte de: |
| id |
todo:paper_15710653_v44_n_p399_Duran |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_15710653_v44_n_p399_Duran2023-10-03T16:27:08Z Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey Durán, G. Balanced graphs Clique graphs Clique-perfect graphs Coordinated graphs K-perfect graphs Perfect graphs A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs. © 2013 Elsevier B.V. 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_v44_n_p399_Duran |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Balanced graphs Clique graphs Clique-perfect graphs Coordinated graphs K-perfect graphs Perfect graphs |
| spellingShingle |
Balanced graphs Clique graphs Clique-perfect graphs Coordinated graphs K-perfect graphs Perfect graphs Durán, G. Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey |
| topic_facet |
Balanced graphs Clique graphs Clique-perfect graphs Coordinated graphs K-perfect graphs Perfect graphs |
| description |
A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs. © 2013 Elsevier B.V. |
| format |
JOUR |
| author |
Durán, G. |
| author_facet |
Durán, G. |
| author_sort |
Durán, G. |
| title |
Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey |
| title_short |
Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey |
| title_full |
Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey |
| title_fullStr |
Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey |
| title_full_unstemmed |
Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey |
| title_sort |
forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: a survey |
| url |
http://hdl.handle.net/20.500.12110/paper_15710653_v44_n_p399_Duran |
| work_keys_str_mv |
AT durang forbiddeninducedsubgraphcharacterizationsofsubclassesandvariationsofperfectgraphsasurvey |
| _version_ |
1807318068419887104 |