Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Problèmes ouverts de coloration et NP-completude
du groupe GT Graphes et Applications

Date 2010-09-17  14:00-15:00
TitreProblè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.  
LieuSalle 76 
OrateurPascal Ochem 
UrlLRI, Orsay 



Aucun document lié à cet événement.

Retour
Retour à l'index