2015/08/19 by Fan Yang, Yang, Fan, Sanming Zhou +1
Computer Science · Mathematics · #05C21 #05C22 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C21 #msc:05C22
paper · pdf · doi:10.48550/arxiv.1508.04620
This paper has been withdrawn by the authors due to an incomplete proof
openalex publication_date 2015/08/19 · arxiv created 2016/04/12 · arxiv updated 2016/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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), …, -1, 1, …, (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 ≥ 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.