Abstrait

Polynômes chromatiques

Karrie Williams

Lorsqu'il s'agit de colorer les nœuds d'un graphe sous des contraintes particulières, il y a beaucoup de difficultés fascinantes à explorer qui fournissent un aperçu rapide des bases de cette section de la théorie des graphes. La coloration d'un graphe est obtenue en attribuant une couleur à chaque nœud du graphe. C'est une traduction des nœuds dans (ou sur) un ensemble s C en termes plus formels (l'ensemble des couleurs). Nous mettrons de côté le débat sur la question de savoir si les mappages doivent être dans l'un ou l'autre pour le moment. Une coloration appropriée d'un graphe est celle qui remplit la contrainte selon laquelle les nœuds adjacents ne sont pas affectés (c'est-à-dire mappés sur) la même couleur (élément) de C. Une coloration qui ne répond pas à ces critères est qualifiée de coloration inappropriée. Telles sont les exigences ; cependant, comme nous aurons presque toujours affaire à des colorations appropriées, il sera plus pratique d'éliminer le mot "approprié" et de convenir que lorsque nous disons "colorations" d'un graphe, nous entendons "colorations appropriées" sauf indication contraire