Loading [MathJax]/jax/output/HTML-CSS/jax.js

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: stable set,independent set,graph colouring,Meyniel graph,perfect graph,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 297 times.
This article's PDF has been downloaded 274 times.