On Z₃-connectivity And Improper Coloring Of Graphs

Tutte first introduced the concept of nowhere-zero flow as a tool to attack the 4-color-conjecture, and posed the famous 3-flows conjecture:every 4-edge-connected graph admits a nowhere-zero 3-flow. Let D be an orientation of a graph G, and let ED+(v)(ED-(v)) denote the edges with tail(head) at v. If there is a map f:E(G)â†' {±1, ±2,..., ±(k-1)} such that for every vertex v ∈ V(G),then G admits a nowhere-zero k-flow. In 1992, Jaeger et al. [25] introduced the concept of graph connectivity of graph as a generalization of nowhere-zero flows. Let A denote an abelian group with the identity element 0. If for any b:V(G)â†'A with ∑v∈V(G) b(v)=0,there is a function f:E(G)â†'A\{0} such that for each vertex v∈V(G),then G is A-connected. In [25], Jaeger et al. conjectured that every 5-edge-connected graph is Z3-connected. At present, on these two conjectures, numerous studies were extensively made on such two problems whether a graph G admits a nowhere-zero 3-flow or is Z3-connected. Thus, this dissertation does some work as follows.In Chapter 2, Jaeger et al.’s Z3-connected conjecture was reduced to consider-ation of 5-edge-connected claw-free graphs by Lovasz [J. Combin. Theory, Ser. B 103 (2013) 587-598], Lai [Inform. Process. Lett., 111 (2011) 1085-1088] and Ma and Li [Discrete Math.,336 (2014) 57-68]. Let I(u, v) denote the set of common neighbors of two vertices u, v if d(u, v)= 2 in G, that is, I(u, v)= N(u)∩ N(v). Let (?) denote the set of all simple and connected graphs such that G G(?) if and only if G is claw-free and satisfies |IG(u, v)|≥2 for every pair of 2-distance vertices u, v. In this chapter, we show that G is not Z3-connected if and only if G is one of seven specified graphs, or three families of well characterized graphs.In Chapter 3, let G be a 2-edge-connected simple graph on n≥4 vertices. For an edge e= uv∈E(G), define d(e)= d(u)+d(v). Let (?) denote the set of all simple 2-edge-connected graphs on n≥4 vertices such that G ∈(?) if and only if d(e)+d(e’)≥2n for every pair of 2-independent edges e, e’ of G when e, e’ exist or d(e)≥n. In this chapter, we prove that for each G ∈F, G is not Z3-connected if and only if G is one of K2,n-2,K3,n-3, K2,n-2+ K3,n-3+ or one of the 16 specified graphs, which generalizes the results of Zhang et al. [[55], X. Zhang et al, Degree sum condition for Z3-connectivity in graphs, Discrete math.310 (2010) 3390-3397].Chapter 4 transfers to focus on a improper coloring problem of a family of planar graphs. Let G be a planar graph and let d1, d2,...,dk be k non-negative integers. A graph G is (d1, d2,..., dk)-colorable if the vertex set can be partitioned into k sets V1,V2,...,Vk, such that the subgraph G[Vi], induced by Vi, has maximum degree at most di for i= 1,2,..., k. Borodin and Raspaud [[10], A sufficient condition for planar graphs to be 3-colorable, J. Combin. Theory, Ser B,88 (2003),17-27] conjectured that every planar graph without adjacent 3-cycles and without 5-cycles is 3-colorable. In Chapter 4, we prove that every planar graph without adjacent 3-cycles and without 5-cycles is (1, 1,0)-colorable, which strengthens the result of Xu [[50], On (3,1)*-coloring of planar graphs, SIAM J. Disceret Math.,23 (2009) 205-220].