Even Pairs

Abstract : Two nonadjacent vertices x and y in a graph G form an even pair if every induced path between them has an even number of edges. Even pairs have become an imprtant tool for proving that certain classes of graphs are perfect and for designing optimization algorithms on special classes of perfect graphs. This chapter surveys results of these types.It also discusses numerous related concepts including odd pairs.