Graphes et algorithmes : documents, bibliographie

Cette carte des régions de france a été coloriée de façon à ce que deux régions voisines aient des couleurs différentes. Ici quatre couleurs ont suffi. Pensez-vous que l'on puisse y arriver avec seulement trois couleurs ? D'une façon générale, peut-on toujours colorier ainsi une carte (ou, de façon équivalente, les sommets d'un graphe planaire) avec seulement quatre couleurs ? Ce problème difficile a été l'objet de recherches actives pendant plus d'un siècle... Pour en savoir plus...