Coloration de graphe
thumb|Une coloration du graphe de Petersen avec 3 couleurs. En théorie des graphes, la coloration de graphe consiste à attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente. On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique. La coloration fractionnaire consiste à chercher non plus une mais plusieurs couleurs par sommet et en associant des coûts à chacune. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications, la conception de puces électroniques ou l'allocation de registres en compilation. Théorème des quatre couleurs Les premiers résultats de coloration de graphe concernent presque exclusivement les graphes planaires : il s'agissait alors de colorier des cartes. En cherchant à mettre en couleurs une carte des comtés d'Angleterre, Francis Guthrie postula la conjecture des quatre couleurs. Il remarqua en effet qu'il n'y avait besoin que de quatre couleurs pour que deux comtés ayant une frontière commune soient de couleurs différentes. Le frère de Guthrie transmit la question à son professeur de mathématiques, Auguste de Morgan de l'University College de Londres. De Morgan mentionna ce problème dans une lettre adressée à William Rowan Hamilton en 1852. Arthur Cayley évoqua cette question lors d'un colloque de la London Mathematical Society en 1879. La même année, Alfred Kempe publia ce qu'il prétendit en être une démonstration et pendant une décennie, on crut que le problème des quatre couleurs était résolu. Kempe fut élu membre de la Royal Society et devint ensuite président de la London Mathematical Society. En 1890, Percy John Heawood fit remarquer que la démonstration de Kempe était fausse. Il montra quant à lui le théorème des cinq couleurs en reprenant des idées de Kempe. De nombreux travaux ont été publiés lors du siècle suivant pour réduire le nombre de couleurs à quatre, jusqu'à la démonstration finale de Kenneth Appel et Wolfgang Haken.
