Coloration équitable

En mathématiques, et en particulier en théorie des graphes, une coloration équitable est l'opération qui consiste à affecter des couleurs aux sommets d'un graphe non orienté (coloration de graphe), de telle manière que :

• deux sommets adjacents n'aient jamais la même couleur
• les nombres de sommets dans les différentes couleurs ne diffèrent que de 1 au plus.

En d'autres termes, la répartition des sommets en différentes couleurs doit être aussi uniforme que possible.

La solution évidente pour obtenir une coloration équitable est de donner à chaque sommet une couleur différente. Néanmoins, cette solution emploie beaucoup plus de couleurs que nécessaire. La plupart du temps, on cherche à obtenir une coloration équitable optimale en minimisant le nombre de couleurs.

Exemples

Une coloration équitable du graphe étoile K_1,5.

Étoile

Le graphe étoile K_1,5 de la figure ci-contre est un graphe biparti complet, et pourrait par conséquent être coloré avec seulement deux couleurs : une pour le centre, et l'autre pour la périphérie. Néanmoins, une des couleurs ne s'appliquerait qu'à un seul sommet tandis que l'autre en concernerait cinq : la répartition des couleurs ne serait pas équitable.

Le plus petit nombre de couleurs dans une coloration équitable de ce graphe est 4, comme le montre la figure : le sommet central est toujours le seul de sa couleur, et il faut donc répartir les cinq sommets restants en au moins trois couleurs différentes de façon qu'aucune couleur ne soit représentée par plus de deux sommets. De manière plus générale, W. Meyer observe qu'il faut $\scriptstyle 1+\lceil n/2\rceil$ couleurs pour colorer de façon équitable une étoile K_1,n.

Le graphe biparti complet K_3,3 ne peut pas être coloré de façon équitable avec 3 couleurs.

Biclique

Un phénomène intéressant apparaît dans le graphe biparti complet K_{n, n}, avec n impair. Ce graphe possède une coloration équitable à deux couleurs, en prenant une couleur pour chacune des deux parties. Néanmoins, il ne possède pas de coloration équitable à n couleurs, alors qu'intuitivement on pourrait s'attendre à ce que ce soit « plus facile » en ayant à disposition plus de couleurs.

En effet, toute partition équitable de ces n couleurs affecte exactement 2 sommets par couleur. On ne peut pas placer ces deux sommets dans des parties différentes, car cela formerait des paires de sommets reliées et de même couleur. On ne peut pas non plus placer que des paires de sommets dans chaque partie, puisque le nombre de sommets dans chaque partie est impair.

Théorème de Hajnal-Szemerédi

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.

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 :

Théorème — Tout graphe de degré maximal Δ peut être coloré de façon équitable avec Δ + 1 couleurs.

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.

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.

Applications

Une justification de l'intérêt pour la coloration équitable a été suggérée par W. Meyer en 1973. 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.

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. Si chaque variable dépend au maximum de Δ autres , 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.

Voir aussi

Source

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Equitable coloring » (voir la liste des auteurs).

Articles connexes

• Coloration de graphe
• Coloration des arêtes d'un graphe
• Cocoloration

Liens externes

• (en) ECOPT A Branch and Cut algorithm for solving the Equitable Coloring Problem