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
Fingerprint
Dive into the research topics of 'Six-flows on almost balanced signed graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver