Geodesic
Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a20,
     author = {Cameron, Kathie and Edmonds, Jack},
     title = {Finding a {Strong} {Stable} {Set} or a {Meyniel} {Obstruction} in any {Graph}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3411},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3411/}
}
TY  - JOUR
AU  - Cameron, Kathie
AU  - Edmonds, Jack
TI  - Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3411/
DO  - 10.46298/dmtcs.3411
LA  - en
ID  - DMTCS_2005_special_250_a20
ER  - 
%0 Journal Article
%A Cameron, Kathie
%A Edmonds, Jack
%T Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3411/
%R 10.46298/dmtcs.3411
%G en
%F DMTCS_2005_special_250_a20
Cameron, Kathie; Edmonds, Jack. Finding a Strong Stable Set or a Meyniel Obstruction in any Graph. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3411. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3411/

Cité par Sources :