Handbook of Graph Theory, Combinatorial Optimization, and Algorithms
This chapter is a survey on perfect graphs with an algorithmic flavor. Our emphasis is on important classes of perfect graphs for which there are fast and efficient recognition and optimization algorithms. The classes of graphs we discuss in this chapter are chordal, comparability, interval, perfectly orderable, weakly chordal, perfectly contractile, and chi-bound graphs. For each of these classes, when appropriate, we discuss the complexity of the recognition algorithm and algorithms for finding a minimum coloring, and a largest clique in the graph and its complement.
Copyright © 2015 from Handbook of Graph Theory, Combinatorial Optimization, and Algorithms by Krishnaiyan “KT” Thulasiraman, Subramanian Arumugam, Andreas Brandstädt, Takao Nishizeki. Reproduced by permission of Taylor and Francis Group, LLC, a division of Informa plc.
Place of Publication
Boca Raton, FL
Hoang, Chinh T. and Sritharan, R., "Perfect Graphs" (2015). Computer Science Faculty Publications. 87.