## Nowhere-zero 3-flows in squares of graphs.(English)Zbl 1018.05031

Electron. J. Comb. 10, Research paper R5, 8 p. (2003); printed version J. Comb. 10, No. 1 (2003).
Let $$D$$ be an orientation (of the edges) of a graph $$G$$ and $$f: E(G) \rightarrow \mathbb{Z}$$ be a function. $$(D, f)$$ is called a $$k$$-flow of $$G$$ if $$|f(e)|\leq k-1$$ for every edge $$e\in E(G)$$ and $\sum_{e\in E^+(v)} f(e) = \sum_{e\in E^-(v)} f(e)$ for every $$v\in V(G)$$, where $$E^+(v)$$ ($$E^-(v)$$) denotes the set of all edges with tails (heads) at $$v$$. A $$k$$-flow $$(D, f)$$ is nowhere-zero if $$f(e)\not= 0$$ for every edge $$e$$ of $$G$$. Tutte’s $$3$$-flow conjecture states that every $$4$$-edge-connected graph admits a nowhere-zero $$3$$-flow.
The square $$G^2$$ of a graph $$G$$ is obtained from $$G$$ by adding all edges joing distance $$2$$ vertices in $$G$$. The authors characterize all squares $$G^2$$ admitting a nowhere-zero $$3$$-flow. It follows from their characterization that if the minimum vertex degree of $$G^2$$ is at least $$4$$ then $$G^2$$ admits a nowhere-zero $$3$$-flow. This confirms Tutte’s conjecture for squares of graphs.

### MSC:

 05C15 Coloring of graphs and hypergraphs 05C20 Directed graphs (digraphs), tournaments 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C75 Structural characterization of families of graphs 90B10 Deterministic network models in operations research

### Keywords:

nowhere-zero flow; squares of graphs
Full Text: