différente par région i à colorier, le domaine de chaque
variable étant un ensemble de 4 couleurs
= { bleu, rouge, vert, jaune }
où voisins 
= vrai si i et j sont 2 régions voisines.
Il s'agit de colorier les différentes régions d'une carte de sorte que si deux régions sont voisines alors elles sont de couleurs différentes. On peut montrer que le nombre maximal de couleurs nécessaires pour colorier une carte plane est 4.
Ce problème est un cas particulier du coloriage des sommets d'un graphe (deux sommets adjacents du graphe doivent toujours être de couleurs différentes). Il s'agit d'un problème NP-complet: il n'existe pas d'algorithme polynomial déterministe pour résoudre ce problème. De nombreux cas concrets se ramènent à ce problème: problème des examens, d'emploi du temps, de classification, ...
différente par région i à colorier, le domaine de chaque
variable étant un ensemble de 4 couleurs
où voisins = vrai si i et j sont 2 régions voisines.