Abstract
In 1983, Bouchet conjectured that every flow-admissible signed graph admits a nowhere-zero 6-flow. By Seymour's 6-flow theorem, Bouchet's conjecture holds for signed graphs with all edges positive. Recently, Rollová et al proved that every flow-admissible signed cubic graph with two negative edges admits a nowhere-zero 7-flow, and admits a nowhere-zero 6-flow if its underlying graph either contains a bridge, or is 3-edge-colorable, or is critical. In this paper, we improve and extend these results, and confirm Bouchet's conjecture for signed graphs with frustration number at most two, where the frustration number of a signed graph is the smallest number of vertices whose deletion leaves a balanced signed graph.
Original language | English |
---|---|
Pages (from-to) | 394-404 |
Number of pages | 11 |
Journal | Journal of Graph Theory |
Volume | 92 |
Issue number | 4 |
DOIs | |
State | Published - 1 Dec 2019 |
Keywords
- frustration number
- integer flow
- signed graph