Coloration de graphes
La coloration de graphes attribue des étiquettes, ou couleurs, aux éléments d'un graphe de manière à ce que les éléments adjacents diffèrent, et étudie le nombre minimal de couleurs requis.
Definition
Une coloration propre d'un graphe est une attribution de couleurs à ses sommets de telle sorte qu'aucun sommet adjacent ne partage la même couleur ; le nombre chromatique est le plus petit nombre de couleurs pour lequel une telle attribution existe.
Scope
Ce sujet aborde la coloration propre des sommets et le nombre chromatique, la coloration des arêtes et l'indice chromatique, le polynôme chromatique qui dénombre les colorations, ainsi que des résultats marquants tels que le théorème de Brooks, le théorème de Vizing et le théorème des quatre couleurs pour les graphes planaires. Il relie la coloration à l'indépendance, aux cliques et à la théorie plus large des paramètres de graphes.
Core questions
- Quel est le nombre minimal de couleurs nécessaires pour colorer proprement un graphe donné ?
- Combien de colorations propres avec une palette donnée un graphe admet-il ?
- Quels graphes peuvent être colorés avec peu de couleurs, et quelles obstructions en exigent beaucoup ?
- Comment les colorations d'arêtes et les colorations par liste étendent-elles la notion de base ?
Key concepts
- Coloration propre des sommets
- Nombre chromatique
- Polynôme chromatique
- Coloration des arêtes et indice chromatique
- Théorème de Brooks
- Théorème des quatre couleurs
Key theories
- Théorème des quatre couleurs
- Tout graphe planaire peut être proprement coloré avec au plus quatre couleurs, une affirmation restée ouverte pendant plus d'un siècle et prouvée pour la première fois par Appel et Haken en 1976 à l'aide d'une analyse de cas extensive assistée par ordinateur.
- Théorème de Vizing
- Les arêtes de tout graphe simple peuvent être proprement colorées avec soit le degré maximal, soit un de plus que le degré maximal de couleurs, divisant ainsi tous les graphes en deux classes étroites.
Clinical relevance
La coloration modélise l'allocation de ressources sans conflit : la planification sans chevauchement, l'allocation de registres dans les compilateurs, l'attribution de fréquences dans les réseaux sans fil et les problèmes de contraintes de type Sudoku se réduisent tous à la coloration de graphes.
History
La conjecture des quatre couleurs, posée en 1852, a largement stimulé la théorie de la coloration ; sa preuve assistée par ordinateur en 1976 par Appel et Haken a constitué une étape majeure précoce dans les mathématiques assistées par ordinateur et a suscité un débat sur la nature de la preuve.
Debates
- Statut des preuves assistées par ordinateur
- La dépendance du théorème des quatre couleurs à des cas vérifiés par machine a soulevé la question de savoir si une preuve trop longue pour être vérifiée manuellement par un humain devait être considérée comme une preuve mathématique authentique.
Key figures
- Kenneth Appel
- Wolfgang Haken
- Vadim Vizing
Related topics
Seminal works
- diestel2017
Frequently asked questions
- Qu'est-ce que le nombre chromatique d'un graphe ?
- C'est le plus petit nombre de couleurs nécessaires pour que les sommets adjacents reçoivent toujours des couleurs différentes ; par exemple, un cycle impair a un nombre chromatique de trois.
- Le théorème des quatre couleurs s'applique-t-il à toutes les cartes ?
- Il s'applique aux cartes dessinées sur le plan ou la sphère où les régions sont connectées ; les cartes sur des surfaces telles que le tore peuvent nécessiter plus de couleurs.