Realizing Degree Sequences with Graphs having 3-Flows


A k-flow in a graph assigns to each edge a direction and a value 0,1, ... ,k-1 such that at each vertex the sum of the flows directed in equals the sum of the flows directed out. The flow is nowhere-zero if zero is not assigned to an edge. For a survey of results on flows, see [J] or [Y].

Suppose that we are given the degree sequence of a graph. A realization of this sequence is a graph with the given degrees. For example, K_4 is the unique realization of the sequence {3,3,3,3}. There are numerous results characterizing which sequences are graphical, that is, of sequences that have a realization.

Conjecture [T1]: Let S be a graphical degree sequence of minimum degree at least 3 that is not {3,3,3,3}. Then S  is realized by a graph that admits a nowhere 3-flow.

The conjecture is stated in terms of integer flows. It is equivalent to consider flows from the integers modulo 3 [T1].

Luo, Zang, and Zhang [LZZ] have shown that every bipartite graphical sequence of minimum degree 2 is realized by a graph with a nowhere-zero 4-flow.

References:

[J] F. Jaejer, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979) 205-216.

[LZZ] R. Luo, W. Zang, and C.Q. Zhang, Nowhere-zero 4-flows, simultaneous edge-colorings, and critical partial Latin squares, preprint.

[T1] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80-91.

[Y] D.H. Younger, Integer flows, J. Graph Theory 7 (1983) 349-357.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.

Send comments to dan.archdeacon@uvm.edu

November 2003.