Nowhere-zero5-flow And Related Problems

In1954, Tutte created the integer flow theory which generalized the face coloring problems in graphs. The integer flow theory has became one of crucial tools to deal with some coloring problems. Tutte proposed several famous integer flow conjectures. One of them is the following5-flow conjecture which is still open.5-Flow Conjecture:Every bridgeless graph has a nowhere-zero5-flow.The5-flow conjecture has been widely studied, and it leads a multitude of significate results in integer flow theory.This thesis studies the5-flow conjecture. The main result states that a cycli-cally6-edge-connected cubic graph G has a nowhere-zero5-flow if G has two parity subgraphs with at most two common edges. This generalizes Jaeger and Steffen’s results.Chapter one introduces some terminology and notations in graph theory, and also introduces the background and significance of5-Flow Conjecture.Chapter two introduces some basic concepts and theorems in integer flow theory, and surveys some advances in Integer Flow Conjectures(3-flow conjec-ture,4-flow conjecture,5-flow conjecture), and also gives proves for some classical results.Chapter three gives main result in this thesis. A parity subgraph of a graph is a spanning subgraph such that the degrees of each vertex have the same parity in both the subgraph and the original graph. Let G be a cyclically6-edge-connected cubic graph. Steffen (2012) proved that G has a nowhere-zero5-flow if G has two perfect matchings with at most two intersections. This chapter shows that G has a nowhere-zero5-flow if G has two parity subgraphs with at most two common edges, which generalizes Steffen’s result. The main tools used in the proof are Jaeger’s balanced valuation formula, some properties of3-colorable graph, connectivity and Menger’s theorem.