Z₃-connectivity In Triangle-free Graph

The development of graph theory starting from euler solved seven bridge problem in 1736,has nearly three hundred years of history.During this period,many branches appeared.These branches are related to two directions,one is the development of graph theory itself,for example,graph coloring,graph polynomial,graph factor,ergodic,connectivity,matching,plan,ramsey,figure counting theory,and the theory of graph reconstruction.The other is crossing subjects,mainly including algebraic graph theory,the topology theory,geometry graph.,extremum graph theory and probability graph theory and matroid theory etc.In recent years,the study of graph theory is more active.Integer flow is an important branch of graph theory.In order to solve the Four-color Problem,integer flow was first introduced by Tutte in 1949,and he proved that k-face-coloring of a plan graph gives its a nowhere-zero k-flow.However,instead of plan graphs,Tutte conjectured that 4-edge connected graph exists nowhere-zero 3-flow,2-edge connected graph exists nowhere-zero 5-flow.These became later the famous 3-flow conjecture and 5-flow conjecture and many researching works are based on these two conjectures.Recently,Liliangchen and Lixiangwen study the Z3-connectivity on bipartite graph on the condition ?(G)[n/4]+ 1,n ? 9.Inspired by this,this article will research Z3-connectivity on triangle-free graph.This article is focus on Z3-connectivity of triangle-free graphs.In this paper,we prove that for triangle-free graph G if ?(G)[n/4]+ 1,n ? 9,then G is Z3-connected exception for two 4-regular graphs with 12 vertices,and consequently G has a nowhere-zero 3-flow.The content of this article are divided into three chapters.In first chapter,we mainly introduce the background of integer flow and introduce some basic concept and definitions for integer flow and group connectivity.In second chapter,we study the Z3-connectivity with 9 ? n ? 12 when ? = 4.If n = 9,then G is bipartite graph,we are done.If n = 10,we finished the proof from the definition of group connectivity.If n 11 or 12,we discuss ?(G),by using the method of edge contraction and splitting,we finish the proof.xx In third chapter,we study the Z3-connectivity with 13 ? n ? 16 and ? = 5.If n = 13 or 14,we remove one or two vertices in G,and turn the problem to the situation of n = 12.If n = 15 or 16,we discuss ?(G),by using the method of edge contraction and splitting,we finish the proof.At last,we study the Z3-connectivity with 17 ? n and ?(G)[n/4]+ 1.Combined with the necessary condition m?[n2/4]of the triangle-free graph,we can see G is 6-edge-connected.Further,by the result of Thomassen,we conclude that G is Z3-connected.