Abstract:
La coloration de graphes est un problème classique de la théorie des graphes. Dans
ce mémoire, nous nous intéressons à abordé certainement l’un des plus fameux
sujets de la théorie des graphes : la coloration des sommets. Il s’agit de colorer les
sommets d’un graphe afin que deux sommets adjacents n’aient pas la même couleur. En particulier, nous montrons quelques techniques de coloration des sommets
utilisées dans ce cadre afin d’obtenir des meilleurs résultats.
Un intérêt particulier est porté aux algorithmes cités dans notre projet vu leur
grande efficacité face aux problèmes de la coloration.
Coloring of graphs is a classic problem in graph theory. In this thesis, we are
interested in tackling one of the most famous subjects of graph theory : the coloring
of vertices. This involves coloring the vertices of a graph so that two adjacent
vertices do not have the same color. In particular, we show some vertex coloring
techniques used in this setting in order to obtain the best results. A particular
interest is brought to the algorithms cited in our project given their great efficiency
in the face of coloring problems.
