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