Six-flows on almost balanced signed graphs

Xiao Wang, You Lu, Cun Quan Zhang, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 languageEnglish
Pages (from-to)394-404
Number of pages11
JournalJournal of Graph Theory
Volume92
Issue number4
DOIs
StatePublished - 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