Even pairs (Q2758333)

An even pair in a graph consists of two nonadjacent vertices between which every induced path has an even number of edges. A graph \(G\) is even-contractile if there exists a sequence \(G = G_0, G_1, G_2, \ldots, G_j\) such that \(G_j\) is a clique, \(G_{i+1}\) is obtained from \(G_i\) by contracting an even pair of \(G_i\). A graph \(G\) is perfectly contractile if each of its induced subgraphs is even-contractile. Even pairs are related to perfect and perfectly contractile graphs form an interesting class of perfect graphs. The paper is an update version of the survey [Path parity and perfection, Discrete Math. 165/166, 223-242 (1997; Zbl 0879.05053)] by the same authors.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].