Maximum-degree conjecture for critically frustrated signed graphs

Let (G,σ)(G,\sigma) be a critically kk-frustrated signed graph, and let Δ(G)\Delta(G) denote the maximum degree of GG. A cycle is negative when the product of the signs on its edges is negative.

Maximum-degree conjecture. Every critically kk-frustrated signed graph (G,σ)(G,\sigma) satisfies

Δ(G)2k.\Delta(G)\leq 2k.

Moreover, equality Δ(G)=2k\Delta(G)=2k can occur only when GG consists of kk negative cycles that are pairwise edge-disjoint but all contain the same vertex.

This conjecture proposes both a universal maximum-degree bound and a characterization of the equality case; the source gives no resolution.

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.