Algorithms for perfectly contractile graphs

Abstract

We consider the class $\mathcal{A}$ of graphs that contain no odd hole, no antihole of length at least 5, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them) and the class ${\mathcal{A}}^{\prime }$ of graphs that contain no odd hole, no antihole of length at least 5 and no odd prism (prism whose three paths are odd). These two classes were introduced by Everett and Reed and are relevant to the study of perfect graphs. We give polynomial-time recognition algorithms for these two classes. We proved previously that every graph $G\in \mathcal{A}$ is "perfectly contractile", as conjectured by Everett and Reed [see the chapter "Even pairs" in the book {\it Perfect Graphs}, J.L. Ram\'ırez-Alfons\'ın and B.A. Reed, eds., Wiley Interscience, 2001]. The analogous conjecture concerning graphs in ${\mathcal{A}}^{\prime }$ is still open.

References in corpus (1)

• The strong perfect graph theorem

Cited by in corpus (13)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Detecting induced subgraphs
• Three-in-a-Tree in Near Linear Time
• A Faster Algorithm to Recognize Even-Hole-Free Graphs
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Algorithms for square-$3PC(\cdot ,\cdot )$-free Berge graphs
• Detecting wheels
• The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
• Graphes parfaits : structure et algorithmes
• Finding a Shortest Even Hole in Polynomial Time
• Graphs with no induced wheel or antiwheel
• Coloring Square-free Berge Graphs
• Even pairs in square-free Berge graphs with no odd prism