Evènement pour le groupe
GT Graphes et Applications
Date | 2010-09-17 14:00-15:00 |
Titre | Problèmes ouverts de coloration et NP-completude |
Résumé | Une conjecture bien connue dit notamment que les graphes planaires de maille 8 ont un homomorphisme vers le cycle de taille 5. On montre que si la conjecture est fausse, alors decider si un graphe planaire de maille 8 admet un homomorphisme vers le cycle de taille 5 est un problèmes NP-complet. On donnera aussi des résultats du même genre pour d'autres problèmes ouverts de coloration. |
Lieu | Salle 76 |
Orateur | Pascal Ochem |
Url | LRI, Orsay |
Aucun document lié à cet événement.
RetourRetour à l'index