You are here: Home » Research » Publications Details

Publications of the Department


Mattiolo, Davide, (2021)  - Nowhere-zero Circular Flows e Fattori di Grafi - Costruzioni e Controesempi  - , Tesi di dottorato - (, , Universitą degli studi di Modena e Reggio Emilia ) - pagg. -

Abstract: 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.