Nowhere-zero 3-Flows in Graphs and Signed Graphs

Title Nowhere-zero 3-Flows in Graphs and Signed Graphs


SpeakerProf. Dr. Cun-Quan ZhangWest Virginia University, USA

 14:30-15:30 pm, November 19, 2014



Place: Conference Room B302, Department of Mathematical Sciences


AbstractTutte  observed that every nowhere-zero k-flow on a plane graph gives rise to ak-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow 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-flow.  However, if the surface is non-orientable, then a face-k$-coloring corresponds to a nowhere-zero k-flow 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 flows for graphs and signed graphs. (1) Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. Extended from a recent breakthrough by Thomassen (JCTB 2012) that every 8-edge-connected graphs admits a nowhere-zero 3-flow, it is further proved that every 6-edge-connected graph admits a nowhere-zero 3-flow.(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-flow. This result is further improved for 8-edge-connected signed graphs.


ContactMei Lu