Il polinomio cromatico: colorazioni e orientazioni acicliche di un grafo

Il polinomio cromatico è una funzione associata ai grafi che restituisce il numero di colorazioni proprie di un grafo che si possono ottenere utilizzando al massimo λ colori. Una colorazione propria assegna colori diversi a coppie di vertici adiacenti. L’obiettivo di questo elaborato è esplorare la connessione tra il polinomio cromatico e le orientazioni acicliche di un grafo. In particolare ci focalizzeremo sul teorema di Stanley, che dimostra che il valore assoluto del polinomio cromatico calcolato in -1 corrisponde al numero di orientazioni acicliche del grafo. Presenteremo prima lo studio di Stanley e, successivamente, una dimostrazione alternativa che utilizza le funzioni generatrici. In particolare faremo riferimento a diverse relazioni tra sottoinsiemi di vertici indipendenti, colorazioni proprie e orientazioni acicliche, che ci condurranno alla dimostrazione del teorema. La parte finale sarà dedicata allo studio delle orientazioni acicliche con un insieme fissato di vertici indipendenti come insieme delle sorgenti, e verrà analizzato in particolare il caso in cui tale insieme abbia cardinalità 1.