Flows in graphs: Tutte´s flow conjectures

Specialeforsvar ved Rikke Marie Langhede

Titel: Flows in graphs: Tutte’s flow conjectures

  

Abstract: In this thesis we study flows in graphs. Among the major open problems in modern graph theory are the 5-Flow Conjecture, which states that every bridgeless graph admits a 5-flow, and the 3-Flow Conjecture which states that every 4-edge-connected graph admits a 3-flow. This thesis reviews the most important results in flow theory, including comprehensive proofs and state-of-the-art techniques in the field. We will introduce the standard results in flow theory in order to prove some partial results of the flow conjectures above, for example the 6-Flow Theorem and the reduction of the 3-Flow Conjecture to 5-edge-connected graphs. A particularly important result is the Weak 3-Flow Theorem which was recently proved by Thomassen with bound k=8 on the edge-connectivity. It has afterwards been improved by Lovász et al. with a bound of k=6. We prove the theorem with the smaller of the bounds. Finally, we will consider generalizations of the flow concept to group connectivity, circular flows, and flow with values in a prescribed set, where we will see the extensive consequences the proof of the Weak 3-Flow Theorem has on the field of flow theory.

 

 

Vejleder: Bergfinnur Durhuus
Censor:   Tom Høholdt, DTU