Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184368
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:37:50 AM
Last modification on : Thursday, May 11, 2017 - 1:02:53 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:02:10 AM

File

dmAE0140.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184368, version 1

Collections

Citation

Kathie Cameron, Jack Edmonds. Finding a Strong Stable Set or a Meyniel Obstruction in any Graph. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.203-206. ⟨hal-01184368⟩

Share

Metrics

Record views

308

Files downloads

559