Finiteness conjecture for prime critically frustrated signed graphs

A signed graph (G,σ)(G,\sigma) is a graph with a positive or negative sign on each edge. Its frustration index l(G,σ)l(G,\sigma) is the minimum number of negative edges among signatures switching equivalent to σ\sigma. A signed graph is critically kk-frustrated if l(G,σ)=kl(G,\sigma)=k and deleting any edge decreases the frustration index. It is prime if it is irreducible and contains no pair of edge-disjoint negative cycles. Finiteness conjecture. For every positive integer kk, there are only finitely many prime critically kk-frustrated signed graphs. This is the finiteness question arising from the study of primitive critical signed graphs and the multiple weak 22-linkage problem. The supplied text states that the cases of prime critically 1-frustrated and 2-frustrated signed graphs were subsequently classified, but it does not establish the conjecture for all positive integers kk.

Sources & referencesView supporting material

Primary source

Zhiqian Wang, “Finiteness of non-decomposable critically 4 and 5-frustrated signed graphs”, arXiv:2603.11883 (2026).

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.