Zaslavsky's multipartite graph conjecture for maximum frustration index

Let Kn1,n2,…,nkK_{n_1,n_2,\ldots,n_k} be a complete multipartite graph with k≥3k\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 k≥3k\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}).

References

Primary source

Maximilien Gadouleau and Huiying Zeng, “On the maximum and negative frustration indices of graphs”, arXiv:2606.11108 (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.