Recognition of quasi-Meyniel graphs

We present a polynomial-time algorithm for recognizing quasi-Meyniel graphs. A hole is a chordless cycle with at least four vertices. A cap is a cycle with at least five vertices, with a single chord that forms a triangle with two edges of the cycle. A graph G is quasi-Meyniel if it contains no odd hole and for some x∈V(G), the chord of every cap in G has x as an endvertex. Our recognition algorithm is based on star cutset decompositions.