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.


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
Full Text: EuDML EMIS