Zaslavsky's multipartite graph conjecture for maximum frustration index

From papers

Let Kn1,n2,,nkK_{n_1,n_2,\ldots,n_k} be a complete multipartite graph with k3k\geq 3. Let Kn1,n2,,nk-K_{n_1,n_2,\ldots,n_k} denote the signature in which every edge is negative, and write l(G)l(-G) and lmax(G)l_{\max}(G) for the negative and maximum frustration indices of a graph GG. Zaslavsky's multipartite graph conjecture. Complete multipartite graphs Kn1,n2,,nkK_{n_1,n_2,\ldots,n_k} with k3k\geq 3 attain maximum frustration index when signed all negative, that is,

l(Kn1,n2,,nk)=lmax(Kn1,n2,,nk).l(-K_{n_1,n_2,\ldots,n_k})=l_{\max}(K_{n_1,n_2,\ldots,n_k}).

The conjecture is refuted by the chordal graph K3,1,1K_{3,1,1}, which is also a complete multipartite graph with k=3k=3, since l(K3,1,1)=1<2=lmax(K3,1,1)l(-K_{3,1,1})=1<2=l_{\max}(K_{3,1,1}).

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

Maximilien Gadouleau and Huiying Zeng, “On the maximum and negative frustration indices of graphs”, arXiv:2606.11108 (2026).

Solutions 0

No solutions have been posted yet.