| Title
Daniela Bronner
Le problème de la coloration des sommets d’un graphe est un problème
largement étudié en raison de la simplicité de son
énoncé et de sa complexité théorique.
Une coloration d’un graphe est l’attribution d’une couleur à chaque
sommet du graphe de telle sorte que deux sommets adjacents aient couleurs différentes.
Une coloration est appelée optimale si elle utilise un nombre minimum de
couleurs, appelé nombre chromatique et noté χ(G).
Beaucoup de propriétés structurelles des colorations optimales ont été
trouvées et démontrées. Par contre peu de recherches ont été faites sur
des colorations suboptimales (colorations utilisant plus que χ(G)
couleurs).
Ce travail consistait à continuer la recherche sur les colorations
subotimales et plus en particulier à étudier et découvrir des propriétés
sur des graphes dits oligomatiques.
Un graphe G est appelé oligomatique s’il existe une coloration c :V→
{1,…, χ(G) +p} avec p≥1 telle que │K1(v)│< χ(G), pour tout vєV où K1(v)
est l’ensemble de couleurs vues par le sommet v i.e. la couleur des
voisins et la couleur du sommet v.
Au cours de ce travail des problèmes ouverts ont été résolus et des
propriétés intéressantes sur les graphes oligomatiques ont été
découvertes. Des heuristiques en relation avec les colorations
suboptimales et les graphes oligomatiques ont aussi été élaborées.
|