Document Type
Article
Publication Date
2014
Abstract
Tutte observed that every nowhere-zero $k$-flow on a plane graph gives rise to a $k$-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 nonorientable, 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 paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs.
Digital Commons Citation
Wu, Yezhou; Ye, Dong; Zang, Wenan; and Zhang, Cun-Quan, "Nowhere-Zero 3-Flows in Signed Graphs" (2014). Faculty & Staff Scholarship. 253.
https://researchrepository.wvu.edu/faculty_publications/253
Source Citation
Wu, Yezhou., Ye, Dong., Zang, Wenan., & Zhang, Cun-Quan. (2014). Nowhere-Zero 3-Flows In Signed Graphs. SIAM Journal on Discrete Mathematics, 28(3), 1628-1637. http://doi.org/10.1137/130941687