Coloration K-équitable des sommets de nouvelles classes de graphe.

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.