Utilisateur:Sjulliot/Coloration fractionnaire
La coloration fractionnaire est une branche récente de la théorie des graphes appelée théorie fractionnaire des graphes . C'est une généralisation de la coloration des graphes ordinaire.
Dans une coloration de graphe traditionnelle, une couleur est affectée à chaque sommet d'un graphe, et deux sommets adjacents ne doivent pas avoir la même couleur. Dans une coloration fractionnaire, un ensemble de couleurs est affecté à chaque sommet du graphe. L'exigence relative aux sommets adjacents est toujours valable. Par conséquent, si deux sommets sont reliés par une arête, ils ne doivent pas avoir de couleurs communes.
La coloration fractionnaire de graphes peut être vue comme la relaxation linéaire de la coloration de graphes traditionnelle. En effet, les problèmes de coloration fractionnaire se prêtent beaucoup mieux à une approche de programmation linéaire que les problèmes de coloration traditionnels. [[Catégorie:Coloration d'un graphe]]