Document Type
Book Chapter
Publication Date
2015
Publication Source
Handbook of Graph Theory, Combinatorial Optimization, and Algorithms
Abstract
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.
Inclusive pages
706-747
ISBN/ISSN
9781584885955
Document Version
Published Version
Copyright
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.
Publisher
CRC Press
Place of Publication
Boca Raton, FL
eCommons Citation
Hoang, Chinh T. and Sritharan, R., "Perfect Graphs" (2015). Computer Science Faculty Publications. 87.
https://ecommons.udayton.edu/cps_fac_pub/87
Comments
This material is strictly for personal use. For any other use, the user must contact Taylor & Francis directly at this address: permissions.mailbox@taylorandfrancis.com. Printing, photocopying, or sharing via any means is a violation of copyright.