Coloration équitable

Le degré maximal d'un graphe est la valeur maximale des degrés de ses sommets.

Le théorème de Brooks publié en 1941 affirme qu'un graphe de degré maximal Δ peut être coloré avec Δ couleurs, avec deux exceptions (les graphes complets et les cycles impairs). Néanmoins, cette coloration est en général tout sauf équitable.

Paul Erdős a énoncé en 1964 une conjecture selon laquelle le graphe peut être coloré de façon équitable avec seulement une couleur de plus[2].

Cette conjecture a été prouvée par András Hajnal et Endre Szemerédi en 1970 et porte à présent le nom de théorème de Hajnal-Szemerédi[3] :

Par exemple, le graphe biparti K_{3, 3} présenté plus haut, pour lequel Δ = 3, peut être coloré avec 4 couleurs de façon équitable.

La preuve originelle de Hajnal et Szemerédi était longue et compliquée, mais une preuve plus simple a été donnée par Kierstead et Kostochka en 2008[4].

De nombreux travaux ont été menés depuis la publication de ce théorème, d'une part pour le rendre plus fort quant au nombre de couleurs nécessaires, et d'autre part pour le généraliser. Un certain nombre de conjectures restent ouvertes en ce domaine.

Une justification de l'intérêt pour la coloration équitable a été suggérée par W. Meyer en 1973[1]. Elle concerne les problèmes de planification et d'emploi du temps. Dans ce contexte, les sommets du graphe représentent un ensemble de tâches à mener à bien, et une arête relie deux tâches qui ne peuvent pas être menées en même temps. Une coloration du graphe représente une répartition des tâches en sous-ensembles de tâches qui peuvent être menées simultanément. Le nombre de couleurs correspond au nombre d'étapes temporelles nécessaires pour achever le tout. Pour des questions de répartition de charge, il est souhaitable d'effectuer un nombre égal (ou à peu près égal) de tâches au cours de chaque étape. H. Furmańczyk, dans un article de 2006, mentionne une application particulière de ce type, où l'on associe des cours dans une université à des créneaux horaires de façon à ventiler les cours sur les différents créneaux horaires de façon équitable et à éviter de planifier des paires incompatibles de cours à la même heure[5].

Le théorème de Hajnal-Szemerédi a également été utilisé pour limiter la variance de sommes de variables aléatoires à dépendance limitée[6] - [7]. Si chaque variable dépend au maximum de Δ autres [8], une coloration équitable du graphe de dépendance peut être utilisée pour répartir les variables en sous-ensembles indépendants, au sein desquels on peut calculer des inégalités de Chernoff, ce qui a pour résultat une limitation globale plus étroite de la variance que si la répartition avait été non équitable.