Nowhere-zero Circular Flows e Fattori di Grafi - Costruzioni e Controesempi

Nowhere-zero integer flows in graphs represent a research field of great interest in structural graph theory. One of the main reasons is the fact that they generalize the concept of face-coloring of planar graphs. Recall that one of the most famous theorems of graph theory is for sure the 4-Color Theorem (1976), claiming that every bridgeless planar graph admits a proper face-4-coloring. In 1954, Tutte proved that a planar graph has a proper face-k-coloring if and only if it has a nowhere-zero k-flow and conjectured that every bridgeless graph admits a nowhere-zero 5-flow. This conjecture is known as the 5-Flow Conjecture and is one of the most important and outstanding open problems in this area of mathematics. It is well known that the 5-Flow Conjecture is equivalent to its restriction to snarks, that are non-3-edge-colorable cubic graphs with further technical requirements on the girth and cyclic edge-connectivity. Many other important long-standing conjectures can be reduced to the family of snarks and this is the main reason why snarks are studied in many papers. In this dissertation, we study nowhere-zero circular flows, that are a generalization of nowhere-zero integer flows, and, in particular, we study the circular flow number of graphs. Indeed, in the last decades, circular flows have attracted many authors and now some problems and conjectures are left open in this field. The results that appear in the present thesis are motivated by these new problems and conjectures, which in some cases we partially or fully answer to. Most of such results are constructions of infinite families of snarks and, more generally, graphs having specific structural properties. We remark that a few of such families are the first known examples having certain properties, and others contain counterexamples to open research problems.

Uno dei campi di ricerca di grande interesse nella teoria dei grafi strutturale è quello dei nowhere-zero integer flows. Una delle ragioni principali è il fatto che questi oggetti generalizzano il concetto di colorazione propria sulle facce di grafi planari. Si ricordi il Teorema dei 4-Colori del 1976, uno dei teoremi più famosi della teoria dei grafi, che afferma che ogni grafo planare senza ponti ammette una 4-colorazione propria sulle facce. Nel 1954, Tutte dimostrò che un grafo planare ammette una k-colorazione propria sulle facce se e solo se ammette un nowhere-zero k-flow e congetturò che ogni grafo senza ponti ammette un nowhere-zero 5-flow. Questa congettura, conosciuta come la Congettura dei 5-Flussi di Tutte, è uno dei problemi aperti più importanti in quest'area della matematica. È ben noto che la Congettura sui 5-Flussi è equivalente alla sua restrizione agli snarks, grafi cubici che non ammettono una 3-colorazione propria sugli spigoli e con ulteriori restrizioni sulla cintura e connettività ciclica. Molte altre congetture importanti possono essere ridotte alla classe degli snarks e questo è uno dei motivi principali per cui questi grafi sono studiati in molti articoli. In questa tesi studiamo i nowhere-zero circular flows, che sono una generalizzazione dei nowhere-zero integer flows, e, in particolare, studiamo il numero di flusso circolare di grafi. Infatti, negli ultimi decenni, i nowhere-zero circular flows hanno attratto molti autori ed ora, in questo campo, si trovano parecchi problemi di ricerca e congetture aperte. I risultati presentati in questa tesi sono motivati da queste nuove congetture, che in alcuni casi risolviamo in modo parziale o completo. La maggior parte di tali risultati sono costruzioni di famiglie infinite di snarks e, più in generale, grafi con determinate proprietà strutturali. Sottolineiamo che alcune famiglie presentate sono i primi esempi noti aventi determinate caratteristiche mentre altre contengono controesempi a problemi aperti.