The 6-cover conjecture for flow-admissible signed graphs

A signed graph (G,Σ)(G,\Sigma) consists of a graph GG and a set ΣE(G)\Sigma\subseteq E(G) of negative edges. A signed circuit is either a balanced circuit, containing an even number of edges of Σ\Sigma, or a barbell, consisting of two unbalanced circuits sharing exactly one vertex or two vertex-disjoint unbalanced circuits joined by a minimal path. The signed graph is flow-admissible if every edge belongs to a signed circuit.

6-cover conjecture. Every flow-admissible signed graph has a family of signed circuits such that every edge belongs to exactly 66 members of the family.

This extends the circuit-cover problem from ordinary bridgeless graphs to signed graphs. It is known that flow-admissible signed graphs with no kk-cover exist for every positive integer k5k\leq 5; the conjecture asserts that 66 is sufficient, while its truth remains open.

Sources & referencesView supporting material

Primary source

Bo Bao, Rong Chen and Genghua Fan, “Circuit Covers of Signed Eulerian Graphs”, arXiv:1910.09999 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.