Even Pairs

Two non-adjacent vertices in a graph form an even pair if every chordless path between them has an even number of edges. The salient fact about even pairs is that contracting an even pair in a graph G yields a graph that has the same clique number and chromatic number as G. It follows that (a) the contraction of two vertices that form an even pair in a perfect graph produces a new perfect graph, and (b) no minimal imperfect graph can contain an even pair. Fact (a) can be exploited to devise simple combinatorial algorithms for coloring many perfect graphs. Fact (b) can be used to define large classes of perfect graphs. We will review the wealth of results that have appeared on these topics and discuss various related concepts such as odd pairs. This is an updated version of [H. Everett, C.M.H. de Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, B.A. Reed, Path Parity and Perfection, Discrete Mathematics, 165-166 (1997), 223-242.