Tra gli argomenti considerati ormai classici nell’ambito della teoria dei grafi rientrano senz’altro i problemi di colorazione e i problemi di decomposizione.
Per quanto riguarda i primi si parla addirittura di teoria cromatica dei grafi, distinguendo in genere se si considerano colorazioni sui vertici o sugli spigoli. Nei problemi di decomposizione si studia la possibilità di spezzare un grafo assegnato in “pezzi” dotati di particolari proprietà. Di fatto si può pensare che le due tipologie di problemi siano facce diverse della stessa medaglia. In altre parole per una assegnata colorazione di un grafo si può andare ad esaminare la struttura costituita dai sottografi determinati dagli oggetti (vertici o spigoli) che hanno ricevuto lo stesso colore. Viceversa, data una decomposizione di un grafo, si può pensare che i sottografi della decomposizione in esame siano oggetti di colore assegnato in una colorazione di qualche tipo (sui vertici o sugli spigoli).
Per quanto riguarda la colorazione sugli spigoli, un risultato fondamentale si deve a Vizing [4] il quale dimostrò una relazione che lega il numero di colori necessari per determinare una colorazione con la valenza massima dei vertici del grafo in esame. Questo teorema consente di suddividere i grafi in due categorie: i grafi di Classe 1 e di Classe 2. I primi sono tali per cui il numero di colori necessari è pari alla valenza massima dei vertici, i secondi invece necessitano di un colore ulteriore rispetto al valore del grado massimo dei vertici del grafo.
Di notevole importanza è il concetto di 1-fattorizzazione, con il quale si intende la possibilità di decomporre il grafo dato in sottografi ricoprenti regolari di grado 1 tali che, a due a due, siano privi di archi comuni e la loro unione sia il grafo in esame. Il legame tra 1-fattorizzazione e colorazione sugli spigoli emerge in particolare quando si analizzano i grafi regolari; infatti per questi ultimi essere di Classe 1 equivale ad essere 1-fattorizzabili. Affinchè un grafo sia 1-fattorizzabile è necessario, come verrà meglio spiegato nel Cap. 3, che sia regolare e abbia un numero pari di vertici.
Non tutti i grafi regolari però risultano 1-fattorizzabili, come si vede analizzando, ad esempio, il grafo di Petersen. Nasce quindi il problema di determinare una condizione sufficiente che indichi se il grafo è 1-fattorizzabile (e quindi di Classe 1). In particolare è stata sviluppata l’idea che se un grafo regolare ha valenza “abbastanza” alta, allora è 1-fattorizzabile.
Qual’è un valore adeguato per la soglia minima della valenza? È in questo contesto che viene formulata la cosiddetta “congettura della 1-fattorizzazione”, che a tutt’oggi non ha ancora un controesempio:
se G è un grafo regolare di grado d su 2n vertici tale che
• d ≥ n – 1, se n è pari
• d ≥ n,, se n è dispari
allora G è 1-fattorizzabile. Nel tempo si sono dimostrati vari risultati che tendono ad abbassare la soglia, avvicinandosi sempre più a quella della congettura. In questa tesi verranno riportati i risultati relativi ai grafi regolari di grado d = 2n – 1, d = 2n – 2, d = 2n – 3, d = 2n – 4 e d = 2n – 5 presenti in [3] e in [1].
Verranno presentati anche teoremi dovuti a Chetwynd ed Hilton nei quali la congettura in esame è stata dimostrata per d ≥ 6/7 |V (G)|∼0.857 |V (G)| in [1] e d ≥ 1/2(√7 – 1)|V (G)|∼ 0.823 |V (G)| in [2]. Infine verranno elencati alcuni risultati recenti che migliorano la soglia minima che deve soddisfare la valenza del grafo affinchè quest’ultimo sia 1-fattorizzabile.
[1] A. G. Chetwynd, A. J. W. Hilton, Regular graphs of high degree are 1-fatorizable. Proc. London Math. Soc. 3(2), 193-206 (1985)
[2] A. G. Chetwynd, A. J. W. Hilton, 1-factorizing regular graphs of high degree-an improved buond. Discrete Mathematics 75, 103-112 (1989)
[3] W. D. Wallis, One-Factorizations (Kluwer Academic Publishers, Dordrecht, 1997)
[4] V. G. Vizing, On an estimate of the chromatic class of p-graph [Russian]. Discretyni Analiz 3, 25-30 (1964)