Path parity and perfection (Q1356748)

Two vertices \(x\) and \(y\) in a graph \(G\) form an even pair (odd pair) if every induced \(x\)-\(y\) path has an even (respectively odd) number of edges. It is known that no minimal imperfect graph contains an even pair and it is conjectured that no such graph contains an odd pair. This paper presents an almost self-contained survey of several interesting results and conjectures highlighting the relevance of the even pair concept to perfect graph theory. More specifically, a graph \(G\) is said to be even contractile if there is a sequence of graphs \(G_0=G\), \(G_1\), \(G_2, \dots, G_j=\) a clique, such that \(G_{i+1}\) is obtained from \(G_i\), for \(i\leq j-1\), by the contraction of an even pair. And \(G\) is said to be perfectly contractile if each of its induced subgraphs is even contractile. Perfectly contractile graphs are perfect and the sequence of even contractions leads to efficient algorithms to calculate the chromatic number \(\chi\) and the largest clique size \(\omega\). It is proved that quasi-Meyniel graphs, weakly triangulated graphs, and perfectly orderable graphs are perfectly contractile, and algorithms to calculate \(\chi\) and \(\omega\) for these graphs are discussed. Several conjectures are presented, a prominent one being a characterization: a graph is perfectly contractile if and only if it contains no antiholes, no odd holes and no odd stretchers. Recent progress establishing the validity of this conjecture for planar graphs, claw- free graphs, and bull-free graphs is discussed and a few other conjectures are presented.