Abstract
A Meyniel obstruction is an odd cycle with at least five vertices and at most one chord. A graph is Meyniel if and only if it has no Meyniel obstruction as an induced subgraph. Here we give a O ( n 2 ) algorithm that, for any graph, finds either a clique and a coloring of the same size or a Meyniel obstruction. We also give a O ( n 3 ) algorithm that, for any graph, finds either a strong stable set recognizable in polynomial time or a Meyniel obstruction.