Kathie Cameron ; Jack Edmonds
-
Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
dmtcs:3411 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3411
Finding a Strong Stable Set or a Meyniel Obstruction in any GraphArticle
Authors: Kathie Cameron 1; Jack Edmonds 1
NULL##NULL
Kathie Cameron;Jack Edmonds
1 Department of Mathematics, Wilfrid Laurier University
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.