À propos de la coloration de cartes

Le jeudi 20 février 2025 11h45-13h00, (Chartreuse, salle 8C-244), Valentin Gledel (LAMA, USMB) nous fera un exposé intitulé : “À propos de la coloration de cartes”.

Résumé : Dans cette présentation, nous présenterons le problème de la coloration de cartes avec le moins de couleurs possible. Pour ce faire, nous introduirons la notion de graphe planaire et quelques résultats en théorie des graphes. Ces notions nous permettront d'avoir des algorithmes pour colorier n'importe quelle carte en 5 ou 6 couleurs. Nous parlerons aussi du théorème des quatre couleurs qui affirme que 4 couleurs sont toujours suffisantes. Puis, nous évoquerons des algorithmes pour savoir si une carte peut être coloriée avec 2 ou 3 couleurs. Enfin, nous terminerons en parlant d'applications de la coloration et de problèmes de recherches actuels dans ce domaine.