On planar perfectly contractile graphs (Q1359374): Difference between revisions

Two non-adjacent vertices of a graph \(G\) are called an even pair if every induced path between them has an even number of edges. A graph \(G\) is called perfectly contractile if, for all induced subgraphs \(H\) of \(G\), there exists a sequence of graphs \(H=H_0, H_1,\ldots, H_k\) such that \(H_{i+1}\) arises from \(H_i\) by contracting one even pair, and \(H_k\) is a complete graph. An odd stretcher is a graph obtained from the complement of a chordless cycle with 6 vertices by subdividing the three edges that do not belong to a triangle in such a way that each of the three subdivided paths has an odd length. The authors prove that a planar graph is perfectly contractile if and only if it contains no (induced) cycle of odd length \(> 3\) and no odd stretcher. This result supports the following conjecture (due to H. Everett and B. A. Reed, 1993): A graph is perfectly contractile if and only if it contains no cycle of odd length \(> 3\), no complement of such a cycle, and no odd stretcher. The authors also give a polynomial-time algorithm for the recognition of perfectly contractile planar graphs. Their algorithm makes use of Hsu's decomposition of perfect planar graphs (see\textit{W.-L. Hsu} [Recognizing planar perfect graphs, J. Assoc. Comp. Mach. 34, No. 2, 255-288 (1987)]).