pith. sign in

arxiv: 1508.04620 · v3 · pith:CLLP6VFQnew · submitted 2015-08-19 · 🧮 math.CO

Nowhere-zero 9-flows in 3-edge-connected signed graphs

classification 🧮 math.CO
keywords graphflownowhere-zerosignededgeedgeshalfadmits
0
0 comments X
read the original abstract

A signed graph is a graph with a positive or negative sign on each edge. Regarding each edge as two half edges, an orientation of a signed graph is an assignment of a direction to each of its half edges such that the two half edges of a positive edge receive the same direction and that of a negative edge receive opposite directions. A signed graph with such an orientation is called a bidirected graph. A nowhere-zero $k$-flow of a bidirected graph is an assignment of an integer from $\{-(k-1), \ldots, -1, 1, \ldots, (k-1)\}$ to each of its half edges such that Kirchhoff's law is respected, that is, the total incoming flow is equal to the total outgoing flow at each vertex. A signed graph is said to admit a nowhere-zero $k$-flow if it has an orientation such that the corresponding bidirected graph admits a nowhere-zero $k$-flow. It was conjectured by Bouchet that every signed graph admitting a nowhere-zero $k$-flow for some integer $k \ge 2$ admits a nowhere-zero 6-flow. In this paper we prove that every $3$-edge-connected signed graph admitting a nowhere-zero $k$-flow for some $k$ admits a nowhere-zero $9$-flow.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.