Path parity and perfection Original Research Article

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. For a given pair {x, y} in a graph G, we denote by Gxy the graph obtained from G by contracting x and y. In 1982, Fonlupt and Uhry proved that if G is perfect then so is Gxy. In 1987, Meyniel used this fact to prove that no minimal imperfect graph contains an even pair. In the last eight years, even pairs have become an important tool for proving that certain classes of graphs are perfect and for designing optimization algorithms on special classes of perfect graphs. This paper surveys results of these types. It also discusses numerous related concepts including odd pairs.