Zaslavsky's multipartite graph conjecture for maximum frustration index
Zaslavsky's multipartite graph conjecture for maximum frustration index
Let be a complete multipartite graph with . Let denote the signature in which every edge is negative, and write and for the negative and maximum frustration indices of a graph . Zaslavsky's multipartite graph conjecture. Complete multipartite graphs with attain maximum frustration index when signed all negative, that is,
The conjecture is refuted by the chordal graph , which is also a complete multipartite graph with , since .
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
Sign in to submit a solution.
No solutions have been posted yet.