Séminaire LJK-Modèles et Algorithmes Déterministes: CASYS

 

Le Jeudi 15 Novembre 2007 à 9h45 en Salle 1 - Tour IRMA

 

Séminaire de Vincent JOST (INRIA)

 

Sur quelques problemes de coloration de graphes

 

Résumé:

 

Colorier un graphe c'est donner une couleur a chaque sommet de telle manière que deux sommets voisins ne reçoivent pas la même couleur.

Je discuterai de généralisations de ce problème avec quelques exemples d'applications. Par exemple certains sommets peuvent être coloriés a priori, le nombre de sommets recevant une couleur donnée peut être borné a priori etc.

Pour certains de ces problème, on peut résoudre le problème exactement si le graphe a une structure particulière (graphe d'intervalles).
Ce genre de structure intervient naturellement dans certaines applications.

Je discute de tels résultats en mentionnant aussi des certificats d'optimalité le cas échéant (formules min-max).