Nowhere-zero 3-flow, Z₃-connectivity And Coloring Of Graphs

Tutte introduced the concept of nowhere-zero flows as a tool to attack the 4-color-problem. Let D(G) be an orientation of a graph G, and let ED+(v) and ED-(v) denote the edges with tail and head at v, respectively. If there exists a map f:E(G)â†'{±1,±2,...,±(k-1)} such that for each vertex u ∈ V(G), then G has a nowhere-zero k-flow. In 1976, Tutte conjectured that every 4-edge-connected graph has a nowhere-zero 3-flow. In 1992, Jaeger et al. [21] extended the concept of nowhere-zero flows to group connectivity of graphs. We denote A by an abelian group with the identity element 0. If for each function b:V(G)â†' A with ΣvEV(G) b(u)=0, there exists a function f:E(G)â†'A-{0} such that for each vertex v E V(G), then G is A-connected. In [21], Jaeger et al. put forward the conjecture:Every 5-edge-connected graph is Z3-connected.Let d1,d2,…,dk be k nonnegative integers, a graph G is improperly (d1, d2,…,dk colorable if the vertex set of G can be partitioned into k sets V1,V2,…,Vk such that the subgraph G[Vi] has maximum degree at most di for i=1,…, k. In 2003, Borodin and Respaud [6] made the following Bordeaux Conjecture:Every planar graph with d▽≥1 and without 5-cycles is 3-colorable, where dâ–½ denote the maximal distance between triangles. Up to now, this challenge conjecture is still open.On these three conjectures, this dissertation does some work as follows.Firstly, we investigate nowhere-zero 3-flow of claw-free simple graph. Let N1,1,0 denote the graph obtained from a 3-cycle u1u2u3u1 by adding two distinct vertices u1 and u2, together with two edges u1u1 and u22u2. If a graph G* is obtained by repeat-edly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say G can be A-reduced to G*. Let G be a simple 2-connected {claw,N1,1,1,0}- free graph. We prove that G does not admit nowhere-zero 3-flow if and only if G can be Z3-reduced to one graph of y, or G is one of G1,G2, G3, G4, G5 in Fig.2-4, or G ∈ (?).Secondly, we investigate Z3-connectivity of claw-free simple graphs without induced cycle of length at least 5. Let G be a 4-edge-connected, K1,3-free simple graph. If G does not contain any induced cycle of length at least 5, then G is Z3-connected.Finally, we investigate (1,1,1)-coloring of planar graphs with neither 6-cycles nor close triangles. It is well-known that the problem of deciding whether a planar graph is properly 3-colorable is NP-complete. The classical colorability of graphs was generalized to improper colorability. We prove that every planar graph with d▽≥1 and without 6-cycles is (1,1,1)-colorable.