Nowhere-zero 3-flows in squares of graphs
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.
scientific article; zbMATH DE number 1862497