La structure de base de notre logo est un graphe. Un graphe est un ensemble de sommets, certaines paires étant reliées par une arête. Le graphe ci-dessus est le graphe Petersen, nommé pour le mathématicien danois du 19e siècle, Julius Petersen.

Le coloriage approprié des sommets est fait lorsque n'importe quelle paire de sommets joints par une arête sont de couleurs différentes. Le coloriage approprié des arêtes est fait lorsque les arêtes aboutissant au même sommet sont de couleurs différentes. Le coloriage total d'un graphe est fait lorsqu'il y a coloriage approprié des sommets et des arêtes, de même que les sommets et les arêtes adjacents sont de couleurs différentes.

Notre logo est colorié totalement à l'aide de cinq couleurs; vous pouvez vous essayer et voir si quatre couleurs sont suffisantes. En général, le nombre de couleurs minimum requiesces pour colorier un graphe est un problème qui n'a pas encore été résolu. Si le degrée d'un sommet est le nombre d'arêtes qui y touchent, on peut donc voir que, pour un coloriage total, le nombre de couleurs requiesce sera le plus grand degrée + 1. On peut être assuré d'un coloriage total en utilisant le plus grand degrée + 2 couleurs.

Les problèmes de coloriage de graphe se réfèrent au problème fondamental de partage d'ensembles d'objets en groupes d'après certaines règles. Ces problèmes ont des applications pratiques dans l'élaboration de schédules et d'horaires.