Finiteness conjecture for non-decomposable critically frustrated signed graphs

Let (G,σ)(G,\sigma) be a signed graph. A signed graph is critically kk-frustrated when its frustration index is kk and decreases after the removal of any edge; it is non-decomposable when it is not an edge-disjoint union of critically frustrated signed graphs and is not obtained from another critically frustrated signed graph by subdivision. Let L(k)\mathcal{L}^*(k) denote the family of irreducible non-decomposable critically kk-frustrated signed graphs.

Finiteness conjecture. For every positive integer kk, the set L(k)\mathcal{L}^*(k) is finite.

The cases k=1k=1 and k=2k=2 are explicitly classified, but finiteness for general positive integers remains open. This conjecture is also stated informally in the introduction and formally later in the paper.

Sources & referencesView supporting material

Primary source

Chiara Cappello, Reza Naserasr, Eckhard Steffen and Zhouningxin Wang, “Critically 3-frustrated signed graphs”, arXiv:2304.10243 (2023).

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.