Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
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...
Main Authors: | Kathie Cameron, Jack Edmonds |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/3411/pdf |
Similar Items
-
Colouring random geometric graphs
by: Colin J. H. McDiarmid, et al.
Published: (2005-01-01) -
Largest cliques in connected supermagic graphs
by: Anna Lladó
Published: (2005-01-01) -
(k − 2)-linear connected components in hypergraphs of rank k
by: Florian Galliot, et al.
Published: (2023-11-01) -
On Kerov polynomials for Jack characters (extended abstract)
by: Valentin Féray, et al.
Published: (2013-01-01) -
Equivalent Subgraphs of Order $3$
by: Tomoki Nakamigawa
Published: (2005-01-01)