Bertschi called a graph G even-contractile if there exists a sequence of even-pair contractions that turn G into a clique, and he called a graph G perfectly contractile (PC) if every induced subgraph of G is even-contractile. Many classical families of graphs (Meyniel graphs, weakly chordal graphs, perfectly orderable graphs, etc) are perfectly contractile, and for some of them (Meyniel graphs, weakly chordal graphs) the coloring algorithm based on even-pair contractions is the most efficient that is known so far.
Everett and Reed conjectured that a graph is PC if and only if it contains no odd hole, no antihole, and no odd prism (two disjoint triangles with three disjoint chordless odd paths between them).
Maffray and Trotignon proved a weaker form of this conjecture, also due to Everett and Reed: if a graph contains no odd hole, no antihole, and no prism, and it is not a clique, then the graph admits an even pair whose contraction yields a graph with no odd hole, no antihole, and no prism. The proof is an algorithm to find such a pair. Here is a link to a [preprint].
The same authors found a polynomial-time algorithm to decide if a graph belongs to that class (the class of graphs with no odd hole, no antihole, and no prism). Here is a link to a [preprint].
Contributed by Frédéric Maffray
Back to the
main index
for Perfect Graphs.