DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional