Fattorizzazione di grafi

tesi di dottorato, relatore: PROF. MICHELE CONFORTI (Dipartimento di Matematica, Universitá di Padova), controrelatore: PROF. BERT GERARDS (Istituto di Ricerca CWI, Amsterdam). Innanzittutto devo segnalare che la mia tesi di dottorato aveva toccato questo argomento fornendo dei contributi originali. Il materiale in essa contenuto e riguardante la Fattorizzazione di grafi ha in gran parte trovato spazio in alcuni dei seguenti lavori.

ROMEO RIZZI,
Indecomposable r-graphs and some other counterexamples,
Journal of Graph Theory 32 (1) (1999) 1-15.
descrizione: Un r-grafo é un punto intero nel cono generato proiettando il politopo dei matching perfetti in un grafo completo. Noi diamo dei controesempi a delle congetture di Seymour e di altri ricercatori e mostriamo come le altezze per le basi di Hilbert di questi coni non siano limitate da costante alcuna. Paul Seymour in persona mi ha chiesto di sottomettere questo lavoro al suo giornale spendendo significativi apprezzamenti.

ROMEO RIZZI,
Finding 1-factors in bipartite regular graphs, and edge-coloring bipartite graphs,
submitted
descrizione: Questo lavoro migliora ulteriormente lo stato del problema di colorare gli archi in un grafo bipartito con al piú $\Delta$ colori. Il collo di bottiglia per la complessitá computazionele dell'algoritmo proposto da Kapoor e Rizzi in ``Edge-coloring bipartite graphs'' era la procedura presa in prestito da Hopcroft e Cole per il reperimento di un accoppiamento perfetto in un grafo bipartito e regolare. Qui si migliora su questa procedura grazie a degli argomenti algebrici. In lavoro mette in luce il legame tra la fattorizzazione di grafi e la fattorizzazione di numeri interi.

ROMEO RIZZI,
Impaccando T-tagli e T-giunti,
Bollettino Sezione B dell'Unione Matematica Italiana,
Fascicolo speciale dedicato alle tesi di dottorato (8) 1-A Suppl. (1998) 201-204.
descrizione: L'UMI offriva uno spazio di 4 pagine per presentare la tesi di dottorato nel suo prestigioso bollettino. In italiano, e con delle figure, ho cercato di attirare l'attenzione del lettore introducendo solo un paio dei problemi affrontati nella mia tesi. Risultato? Un successo: qualcuno ha risposto chiedendomi copia della tesi.

ROMEO RIZZI,
Konig's Edge Coloring Theorem without augmenting paths,
Journal of Graph Theory 29 (1998) 87.
descrizione: Il teorema dei balli é uno di quei risultati con cui Konig ha posto le basi della teoria dei grafi per come oggi é conosciuta. Il teorema ha applicazioni dirette in problemi di scheduling e timetabling, ma anche in discipline piú lontane come la statistica. Nonostante la sua importanza, il risultato veniva derivato come corollario di un'altro fondamentale teorema di Konig. Noi introduciamo un'operazione elementare che trasforma un grafo bipartito e $\Delta$-regolare in un suo fratellino minore. La dimostrazione é ora per induzione ed é diretta.

ROMEO RIZZI,
On packing T-joins,
in preparation
descrizione: Investighiamo il legame tra il problema della fattorizzazione di r-grafi ed il problema dell'impaccamento di T-joins.