FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 12, 17:00 ~ 17:30 - Room B11
Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs
Guillermo Durán
University of Buenos Aires, Argentina - gduran@dm.uba.ar
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 three subclasses of perfect graphs, coordinated graphs, balanced graphs, and neighborhood perfect graphs.