The Research On 3-flow Conjecture

Graph theory is a jumped-up subject which develops very rapidly in recent years and is applied extensively. Many practical problems can be solved through graphs. The graph coloring problem is one of the most famous NP-complete problems. It is a basic method which can be applied in solving some practical problems about task allocation such as transportation problem, time table prob-lem, circuit design and storage problem. In 1950, Tutte initiated that a plan graph is face-κ-colorable if and only if it exists a nowhere-zero κ-flow. There-fore, he introduced nowhere-zero integer flow theory as a tool to study coloring problem and he proposed some related conjectures. Hence, the coloring problem can be converted into an integer flow problem to research. So the integer flow problem became an important problem in graph theory research.Nowhere-zero 3-flow is a spacial case of nowhere-zero integer flow and a lot of works are related to it. The most familiar one is Tutte’s 3-flow conjecture which said that every 4-edge connected graph admits a nowhere-zero 3-flow.3-flow Con-jecture is regarded as a beautiful conjecture in graph theory world. Many famous mathematicians work on this subject, and get a lot of very nice results. But 3-flow Conjecture has not been solved yet. Recently, the Weak 3-flow Conjecture has been solved, which blaze a way in solving 3-flow conjecture.Depending on the known results, we study the Z3-connectivity of graphs, which are stronger than the existence of 3-flow. At the same time, we investi-gate the property of minimum counterexample to the equivalent version of 3-flow conjecture. This is helpful to solve 3-flow conjecture in another direction. In this thesis, the main content is divided into three chapters.In Chapter 1, we firstly introduce some basic concepts and definitions of in-teger flow, and then we give some existing results about 3-flow and the equivalent version of 3-flow.In Chapter 2, we focus on the Z3-connectivity of a special family of graphs, which consists of simple bipartite graphs on 12 vertices with minimum degree 4. This result completes the existing result about Z3-connectivity of bipartite graphs with minimum degree[n/4]+1.In Chapter 3, we mainly describe the graphical feature of a minimal coun-terexample of a equivalent version of 3-flow conjecture. By considering the mini-mum counterexample to 3-flow Conjecture, we study 3-flow Conjecture in another direction.