Vous organisez un colloque dans lequel plusieurs conférences sont données simultanément (dans des salles différentes et à des horaires imposés par les orateurs) et vous cherchez à occuper le moins de salles possibles (car vous devez les louer). Une méthode permettant de réaliser un tel planning consiste à construire un grapheG dans lequel les conférences seront représentées par des sommets tandis que le fait que deux conférences se tiennent, au moins en partie, en même temps sera symbolisé par une arête reliant les deux sommets associés.
On cherche à affecter une salle (repérée par un numéro) à chaque conférence, de telle sorte que deux conférences adjacentes (reliées par une arête) ne soient pas dans la même salle. Une telle affectation est appelée une coloration et le nombre de couleurs est au moins égal au plus grand nombre W(G) de sommets de G deux à deux adjacents. Par exemple, un cycle (graphe dont les sommets sont reliés uniquement à leur prédécesseur et leur successeur) est coloriable en 2 (nombre pair de sommets) ou 3 (nombre impair de sommets) couleurs.
Le graphe précédent est un graphe d'intervalle et […]
