### Finding a Strong Stable Set or a Meyniel Obstruction in any Graph

*Kathie Cameron, Jack Edmonds*

#### Abstract

A strong stable set in a graph G is a stable set that contains a vertex of every maximal clique of G. A Meyniel obstruction is an odd circuit with at least five vertices and at most one chord. Given a graph G and a vertex v of G, we give a polytime algorithm to find either a strong stable set containing v or a Meyniel obstruction in G. This can then be used to find in any graph, a clique and colouring of the same size or a Meyniel obstruction.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page