Groupe graphes
2002-2003

Le dîner scientifique

Le dîner

Un premier graphe
de compatibilité

Un graphe d’incompatibilité…

L’algorithme de
Powell – Welch

Constitution des tables

Remarques…

Autour de l’algorithme de P -W

Un algorithme parfois « glouton »

Une explication…

Un exemple où l’algorithme de Powel-Welsh donne systématiquement un nombre de couleurs supérieur au nombre chromatique…

MAIS…

Et pour terminer, colorons la France…

4 couleurs suffisent pour colorer un graphe planaire…

Graphes complets…

4 couleurs suffisent…

Le nombre chromatique est bien 4…

Diapositive 19