Abstract

Tutte observed that every nowhere-zero k-ow on a plane graph gives rise to a k-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer ow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph G has a face-k-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero k-ow. However, if the surface is non-rientable, then a face-k-coloring corresponds to a nowhere-zero k-ow in a signed graph arising from G.Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive.

In this talk, we present two recent results about integer ows for graphs and signed graphs. (1) Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-ow. Extended from a recent breakthrough by Thomassen (JCTB 2012) that every 8-edge-connected graphs admits a nowhere-zero 3-ow, it is further proved thatevery 6-edge-connected graph admits a nowhere-zero 3-ow. (Joint work with Lovasz, Thomassen and Y. Z. Wu). (2) By applying the above result for graphs, Zhu proved that every 11-edge-connected signed graph admits a nowhere-zero 3-ow. This result is further improved for 8-edge-connected signed graphs. (Joint work with Y.Z. Wu, D. Ye and W. Zang.)