We consider the class A of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them). We prove that every graph G E V different from a clique has an "even pair" (two vertices that are not joined by a chordless path of odd length), as conjectured by Everett and Reed ["Even pairs", in: J.L. Ramirez-Alfonsin, B.A. Reed (eds.), Perfect Graphs, Wiley Interscience, New York, 2001]. Our proof is a polynomial-time algorithm that produces an even pair with the additional property that the contraction of this pair yields a graph in A. This entails a polynomial-time algorithm, based on successively contracting even pairs, to color optimally every graph in A. This generalizes several results concerning some classical families of perfect graphs. (c) 2005 Elsevier Inc. All rights reserved.
展开▼
