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 GraphConference paper

Authors: Kathie Cameron 1; Jack Edmonds 1

  • 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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] stable set, independent set, graph colouring, Meyniel graph, perfect graph

1 Document citing this article

Consultation statistics

This page has been seen 373 times.
This article's PDF has been downloaded 335 times.