Quelques techniques de coloration des sommets dans un graphe

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.