(Exemple tiré d'un exercice de Bac) Supposons que 10 groupes de supporters de différents pays soient présents lors d'une coupe du monde de football. Afin d'éviter les tensions, on veut loger les groupes dans un nombre minimum d'hotels mais en évitant d'y loger des groupes incompatibles. En dressant le graphe des groupes incompatibles (on les relie entre eux s'ils le sont), on peut alors, en determinant le nombre chromatique du graphe, en déduire le nombre minimum d'hotels à réserver et quels groupes loger dans chaque hotel.
Peut-être qu'au lycée ça semble peu utile c'est vrai mais en réalité le coloriage de graphe est applicable dans beaucoup de problème ou en tout cas beaucoup de problème se ramène à un coloriage de graphe.