Nowhere-zero \(k\)-flows of supergraphs. (English) Zbl 0984.05031

A nowhere-zero \(k\)-flow (NZ\(k\)F) in a graph \(G\) assigns to every arc \(e\) in some orientation \(D\) of \(G\) a value \(f(e)\), \(0 < f(e) < k\), such that for every vertex \(v\), the sum of the values of the arcs starting in \(v\) equals the sum of the values of the arcs ending in \(v\). Clearly, NZ\(k\)Fs exist only in bridgeless graphs. It is a longstanding conjecture of W. T. Tutte that every bridgeless graph has an NZ5F—the best result in this direction is P. D. Seymour’s theorem saying that every such graph has an NZ6F. Note that for a plane graph, an NZ\(k\)F corresponds to a proper \(k\)-face colouring, and vice versa; and this is where the theory of integer flows (initiated by Tutte) has its origins. Clearly, an arbitrary graph has an NZ2F iff it is Eulerian, and for cubic (\(3\)-regular) graphs \(G\), the following is true: (a) \(G\) has an NZ3F iff \(G\) is bipartite; (b) \(G\) has an NZ4F iff \(G\) has a proper \(3\)-edge-colouring. The authors consider the question how many edges one has to add to a given graph \(G\) to obtain a supergraph \(G'\) on the same vertex set such that it can be guaranteed that \(G'\) has an NZ\(k\)F for \(k = 3,4,5\). Upper bounds for this number of additional edges are established in terms of the number of odd vertices of \(G\), denoted by \(o(G)\). Note that the problem is trivial for \(k = 2\) since it is tantamount to adding \(\frac{1}{2}o(G)\) edges to obtain an Eulerian supergraph. In all cases, the authors first reduce the respective problem to the consideration of connected bridgeless graphs of minimum degree \(> 2\). Then, applying the splitting lemma they show that one can restrict the considerations to cubic graphs. In the case of \(4\)-flows, they also apply Blanuša’s parity lemma. The results obtained are: Let \(G\) be a connected bridgeless graph with \(o(G)\) odd vertices. It suffices to add at most (i) \(\lfloor \frac{o(G)}{4} \rfloor\) edges to obtain \(G'\) which has an NZ3F; (ii) \(\lceil \frac{1}{2} \lfloor \frac{o(G)}{5} \rfloor \rceil\) edges to obtain \(G'\) which has an NZ4F; (iii) \(\lceil \frac{1}{2} \lfloor \frac{o(G)}{7} \rfloor \rceil\) edges to obtain \(G'\) which has an NZ5F.
The authors also show that they are basically on the right track in that it takes a linear function in \(o(G)\) of additional edges to obtain a corresponding supergraph. Namely, they prove that for every positive integer \(s\), there exists a connected bridgeless graph \(G\) with \(o(G) \geq s\) such that one needs to add at least (j) \(\frac{1}{8}o(G)\) edges to obtain \(G'\) which has an NZ3F; (jj) \(\frac{1}{20}o(G)\) edges to obtain \(G'\) which has an NZ4F; (jjj) \(c \cdot o(G)\) edges to obtain \(G'\) which has an NZ5F, for some constant \(c > 0\), and assuming the NZ5F conjecture is false with respect to \(G\).
Finally, one may consider the analogous problems with respect to edge deletion. Observing that deleting an edge creates a similar effect like doubling that edge, it follows that one has to delete at least as many edges as one has to add to obtain a (sub)graph having a corresponding NZ\(k\)F. With respect to determining the exact number of edges to be deleted, added respectively, the following observations are being made. For \(k = 2\) , the corresponding edge deletion problem is tantamount to solving the Chinese postman problem for \(G\), which can be done in polynomial time as shown by Edmonds and Johnson. For \(k = 4\), the corresponding problem of adding edges is NP-complete since it is an NP-complete problem to decide whether a cubic graph has a proper \(3\)-edge-colouring. If Tutte’s NZ5F conjecture is false, then the problem of constructing a smallest possible supergraph having an NZ5F is also NP-complete, as shown by M. Kochol; an analogous conclusion holds with respect to \(3\)-flows.


05C15 Coloring of graphs and hypergraphs
05C99 Graph theory
Full Text: EuDML EMIS