Nowhere-zero 3-Flows in Graphs and Signed Graphs

报告题目 Nowhere-zero 3-Flows in Graphs and Signed Graphs


报告人Prof. Dr. Cun-Quan ZhangWest Virginia University, USA






摘要Tutte  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.


报告人简介 Prof. Cun-Quan Zhang1986年获得加拿大Simon Fraser大学博士学位,曾获美国West Virginia大学分院最佳科研奖和全校最佳科研奖,多次获得美国NSFNSA的项目基金,已发表八十多篇论文并出版专著一本。(http://www.math.wvu.edu/~cqzhang/






XML 地图 | Sitemap 地图