Abstract:
L’objectif de ce manuscrit est d’abordé l’un des plus fameux sujets de la théorie de
graphe qui s’agit de la coloration des sommets pour obtenir un nombre chromatique
minimal. Nous avons donné quelques concepts de base de la théorie de graphe ainsi les
algorithmes de coloration Welsh and Powell, Dsateur, Algorithme de coloration à jeton,
ensuite nous avons caractérisé des nouvelles classes pour lequel nous avons déterminé
inductivement leurs coloration k-équitable optimal des sommets . A la fin, nous avons
implémenté l’algorithme welsh and powell mannuellement et sur le language de
programmation C++ afin de confirmé les résultats trouvé théoriquement.
The objective of this manuscript is to address one of the most famous topics in graph
theory, namely the coloring of vertices to obtain a minimal chromatic number. We gave
some basic concepts of graph theory as well as thez coloring algorithms Welsh and Powell, Dsateur, Token coloring algorithm, then characterized new classes for which we
inductively determined their optimal k-equitable vertex coloring . Finally, we implemented the welsh and powell algorithm manually and in the programming language C++
to confirm the results found theoretically.
