Coloration équitable

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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
  • le nombre d'arêtes 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[modifier | modifier le code]

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

Étoile[modifier | modifier le code]

Le graphe étoile K1,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 à ce qu'aucune couleur ne soit représenté 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 K1,n[1].

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

Biclique[modifier | modifier le code]

Un phénomène intéressant apparaît dans le graphe biparti complet Kn, 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[modifier | modifier le code]

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 (en) et Endre Szemerédi en 1970 et porte à présent le nom de théorème de Hajnal-Szemerédi[3] :

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

Par exemple, le graphe biparti K3, 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.

Applications[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

  1. a et b (en) Walter Meyer, « Equitable coloring », Amer. Math. Monthly, Mathematical Association of America, vol. 80, no 8,‎ 1973, p. 920–922 (liens DOI? et JSTOR?)
  2. (en) Paul Erdős, « Problem 9 », dans M. Fieldler, Theory of Graphs and its Applications, Prague, Czech Acad. Sci. Publ.,‎ 1964, p. 159
  3. (en) A. Hajnal (en) et E. Szemerédi, « Proof of a conjecture of P. Erdős », dans Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland,‎ 1970, p. 601–623
  4. (en) H. A. Kierstead et A. V. Kostochka, « A short proof of the Hajnal-Szemerédi theorem on equitable colouring », Combinatorics, Probability and Computing, vol. 17, no 2,‎ 2008, p. 265–270 (lien DOI?)
  5. (en) Hanna Furmańczyk, « Equitable coloring of graph products », Opuscula Mathematica, vol. 26, no 1,‎ 2006, p. 31–44 (lire en ligne)
  6. (en) Sriram V. Pemmaraju, « Equitable colorings extend Chernoff-Hoeffding bounds », dans Proc. 12th ACM-SIAM Symp. Discrete Algorithms (SODA 2001),‎ 2001 (lire en ligne), p. 924–925
  7. (en) Svante Janson (en) et Andrzej Ruciński, « The infamous upper tail », Random Structures &Algorithms, vol. 20, no 3,‎ 2002, p. 317–342 (lien DOI?)
  8. Comme c'est le cas dans les hypothèses du lemme local de Lovász.

Voir aussi[modifier | modifier le code]

Source[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

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