Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Brooks
Résumé
En mathématiques, et plus particulièrement dans la théorie des graphes, le théorème de Brooks donne une relation entre le degré maximal d'un graphe connexe non orienté et son nombre chromatique.
Selon ce théorème, dans un graphe où chaque sommet a au plus Δ voisins, les sommets peuvent être colorés avec au plus Δ couleurs, sans que deux sommets adjacents n'aient la même couleur, sauf dans deux cas, les graphes complets et les graphes cycles de longueur impaire, qui ont besoin de Δ + 1 couleurs.
Le théorème porte le nom de R. Leonard Brooks, qui en a publié une démonstration en 1941. Une coloration avec le nombre de couleurs décrit par le théorème de Brooks est parfois appelée coloration de Brooks ou Δ-coloration. László Lovász a donné une démonstration plus simple du théorème en 1975.
Il n'est pas très dur de démontrer que, pour tout graphe, χ(G) ≤ Δ + 1. En effet, n'importe quel sommet v possède au maximum Δ sommets voisins, qui dans le pire des cas sont tous de couleur différente. Même dans ce cas, on peut toujours prendre la (Δ + 1)ème couleur pour colorer v. Le mérite de Brooks a été de diminuer cette majoration de 1 unité dans la plupart des cas.
Il existe plusieurs démonstrations du théorème de Brooks. On peut par exemple raisonner par récurrence sur le nombre de sommets du graphe. La démonstration qui suit procède autrement, elle s'appuie sur l'algorithme glouton de coloration des graphes et a donc le mérite de donner des algorithmes pour colorer le graphe (c'est une démonstration constructive).
Cette démonstration a été présentée par Ross Churchley en 2010 d'après les travaux de John Adrian Bondy en 2003. La fin remplace le raisonnement de Bondy par d'autres travaux pour ne pas avoir à faire appel aux résultats concernant les arbres de parcours en profondeur d'abord.
Dans ce qui suit, nous examinons successivement quatre cas :
les graphes non réguliers ;
les graphes réguliers non biconnexes ;
les graphes réguliers biconnexes de degré inférieur à 3 ;
les graphes réguliers biconnexes de degré supérieur ou égal à 3.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.