Teoria dei grafi e polinomio cromatico

L'elaborato riguarda la definizione e il calcolo del polinomio cromatico. Dopo una parte introduttiva volta a fornire alcune basi di teoria dei grafi, si introducono la colorazione dei vertici e il numero cromatico e di questo si dimostrano alcuni risultati rilevanti come il Teorema di Brooks. Si definisce poi il polinomio cromatico di un grafo e si mostra un algoritmo per calcolarlo basato su operazioni di connessione-contrazione o delezione-contrazione di vertici e archi. Si dimostrano alcuni risultati validi per ogni polinomio cromatico e si studia la corrispondenza tra le caratteristiche del polinomio e quelle del grafo associato.