Colorazione Totale di grafi e Congettura di Behzad-Vizing

La colorazione totale di un grafo è l'assegnazione di un colore ad ogni vertice e ad ogni arco tale che nessuna coppia di elementi adiacenti scelta tra gli insiemi di vertici e archi abbia lo stesso colore. La congettura di Behzad-Vizing enuncia che il numero minimo di colori usati per la colorazione totale di un grafo è minore uguale del grado massimo del grafo più due. Questa tesi illustra come è stata dimostrata la congettura per varie classi di grafi e alcune versioni più deboli della congettura.