Conjecture on the unique signed graph realizing ns(4,3)n_s(4,3)

From papers

Let ns(λ,p)n_s(\lambda,p) be the minimum number of vertices of a signed graph with balanced chromatic number at least pp and negative girth at least λ\lambda. Signed-graph extremal conjecture. One has

ns(4,3)=13,n_s(4,3)=13,

and the only signed graph with 1313 vertices, balanced chromatic number 33, and negative girth 44 is the signed graph depicted in the paper's Figure 13. This is the next open case after the known observation ns(3,p)=2p1n_s(3,p)=2p-1; the supplied text gives no proof or resolution of the conjecture.

Progress summary

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

Sources & referencesView supporting material

Primary source

Lujia Wang, “An Erdos-Gallai conjecture for signed graphs”, arXiv:2509.07724 (2025).

Solutions 0

No solutions have been posted yet.