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.
展开▼
机译:Tutte观察到,平面图上的每处零位$ k $流都会导致其对偶的$ k $顶点着色,反之亦然。因此,零位无穷整数流和图形着色可以看作是双重概念。 Jaeger进一步证明,如果图$ G $在可定向的曲面中嵌入了可着色的面$ k $的2单元格,那么它的无处不在的$ k $流动。但是,如果曲面是不可定向的,则面部$ k $着色对应于由$ G $产生的无符号零图形$ k $流。因此,嵌入在可定向曲面中的图形是一种特殊情况,即相应的符号均为正。在本文中,我们证明了,如果8边连接的带符号图承认无处零整数流,那么它就有无处零3流。我们的结果将关于8边连接图的Thomassen的3流定理扩展到所有8边连接的带符号图的族。此外,它还改进了在11个边连接的带符号图上的朱三流定理。
展开▼