Coloration équitable
De Wikipedia, l'encyclopédie encyclopedia
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.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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.