Il polinomio cromatico e le relazioni con le orientazioni acicliche di grafi.

Abstract

La presente tesi si propone di approfondire lo studio del polinomio cromatico di un grafo, analizzandone le proprietà teoriche, le principali applicazioni e i profondi legami strutturali. Partendo dalle nozioni fondamentali di colorazione, l'elaborato si concentra inizialmente sulle operazioni di manipolazione dei grafi, illustrando il metodo di eliminazione-contrazione come strumento cardine per la dimostrazione della natura polinomiale di tale funzione. Successivamente, la ricerca si focalizza sulla determinazione e sull'analisi dei coefficienti del polinomio cromatico, presentando in particolare il Teorema di H. Whitney, che ne offre una rigorosa descrizione combinatoria. Infine, lo studio culmina con l'esame dei risultati di R. P. Stanley, esplorando le connessioni tra il polinomio cromatico e le orientazioni acicliche di un grafo. Viene così fornita un'interpretazione combinatoria della valutazione del polinomio in numeri interi negativi, svelando significati e proprietà topologiche che trascendono il contesto classico delle colorazioni standard.

This thesis aims to explore the chromatic polynomial of a graph in depth, analyzing its theoretical properties, main applications, and deep structural connections. Starting from the fundamental concepts of graph coloring, the work initially focuses on graph manipulation operations, illustrating the deletion-contraction method as a key tool to prove the polynomial nature of this function. Subsequently, the research focuses on the determination and analysis of the coefficients of the chromatic polynomial, presenting in particular H. Whitney's Theorem, which offers a rigorous combinatorial description of them. Finally, the study culminates in the examination of R. P. Stanley's results, exploring the relationships between the chromatic polynomial and the acyclic orientations of a graph. This provides a combinatorial interpretation of the polynomial's evaluation at negative integers, revealing meanings and topological properties that transcend the classical framework of standard colorings.