List 3-Dynamic Colorings And Integer 3-Flows

Graph coloring theory is one of the most fundamental subjects and has a central position in discrete mathematics.The investigation on the 4-Color-Problem shaped graph theory.With the in-depth of study of scholars on coloring problems,various versions of graph coloring have been proposed.The r-dynamic coloring is a generalization of the classical coloring.It was first introduced by Lai et al.The list r-dynamic coloring,as a list version of the r-dynamic coloring,is a generalization of the classical list coloring.It has important theoretical significance.The concept of integer flow was originally introduced by Tutte in 1940s as the dual of graph coloring.It is of great research value.In addition,the concept of flow is a useful model in Operation Research,and it serves as a graph model to represent current in an electrical network,the flow of vehicles and the freight traffic volume in a traffic network and so on.Thus it has vast application prospect.On the basis of previous work,we study the list 3-dynamic chromatic number and nowhere-zero 3-flows of some special graph classes.Let G=(V,E)be an ordinary graph,where V and E denote the set of vertices and edges of G,respectively.A proper k-coloring Φ:V(G)(?){1,2,…,k} of a graph G is an assignment of colors to the vertices of G so that any two adj acent vertices receive distinct colors.An r-dynamic k-coloring of a graph G is a proper k-coloring Φ such that for each vertex v ∈ V(G),either the number of distinct colors in its neighborhood is at least r or the colors in its neighborhood are all distinct,that is,|Φ(NG(v))|≥ min{r,dG{v)}.For a list assignment L={L(v)| v ∈ V(G)} of G,we say that G is r-dynamically L-colorable if there exists an r-dynamic coloring Φ such that Φ(v)∈ L(v)for every v ∈ V(G).A graph G is list r-dynamically k-colorable if for any list assignment L with |L(v)|≥ k for every vertex v,G is r-dynamically L-colorable.The list r-dynamic chromatic number chr{G)of a graph G is the least k such that G is list r-dynamically k-colorable.An ordered pair(D,f)is called a nowhere-zero k-flow of an ordinary graph G if D is an orientation of G and f is a mapping from E(G)to {±1,±2,…,±(k-1)} such that for each vertex v ∈ V(G),∑e∈ED+(v)f(e)-∑e∈ED-(v)f(e)=0.The concept of nowhere-zero integer flows for signed graphs was systematically studied at first by Bouchet in 1983.A signed graph is a pair(G,σ),where G is a graph and σ:E{G)→{1,-1} is a signature of G.Each edge of(G,σ)consists of two half-edges which incident with endpoints of the edge,so an orientation of G assigns each half-edge a direction.Thus,similar to ordinary graphs,an ordered pair(τ,f)is called a nowhere-zero k-flow of a signed graph(G,σ)if τ is an orientation of G and f:E(G)(?){±1,±2,…,±(k-1)}is a mapping such that for each vertex,the sum of the weights of all half edges entering it equals to the sum of the weights of all half edges exiting it,where the weight of each half edge is equal to the wight of the edge in which it is located.This thesis consists of six chapters.In Chapter 1,we introduce some basic nota-tions and terminology,give a survey in the related directions of list r-dynamic colorings and integer flows,and show the main results obtained in this thesis.In Chapter 2,we consider the list 3-dynamic chromatic number of near-triangulations and prove that ch3(G)≤6 for every near-triangulation G.The upper bound is optimal.As a corollary,we also obtain that ch3(G)≤6 for every triangulation G.In Chapter 3,we study the structure and extreme size of 3-flow-critical graphs,and we obtain that for any 3-flow-critical graph G on n vertices,8n-2/5≤|E(G)|≤4n-10,where each equality holds if and only if G is K4.In Chapter 4,we prove that every 4-edge-connected toroidal graph admits a nowhere-zero 3-flow.Tutte in 1972 proposed a conjecture that every 4-edge-connected graph admits a nowhere-zero 3-flow.Hence,this partially confirms the 3-flow conjecture.In Chapter 5,we study the nowhere-zero 3-flow in signed planar graphs.It is proved that every 4-edge-connected signed planar graph with two negative edges ad-mits a nowhere-zero 3-flow.Meanwhile,we obtain an equivalent version of the 3-flow conjecture:every 4-edge-connected signed graph with two negative edges admits a nowhere-zero 3-flow.So our result in this chapter supports the 3-flow conjecture.In Chapter 6,we put forward some problems for further study,together with a simple summary of this thesis.