Realizing Degree Sequences with Graphs having 3-Flows

A

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.