The enumeration conjecture for 3-minimal graphs
A 3-minimal graph is a graph whose relevant Lovász–Schrijver semidefinite-programming hierarchy obstruction has minimal rank three. Two graphs are considered the same when they are isomorphic.
Enumeration conjecture. There are exactly non-isomorphic -minimal graphs.
The computational search found 49 such graphs and provides evidence that the displayed list is complete, but the statement is presented as a conjecture rather than an established theorem.
References
Primary source
Yu Hin Au and Levent Tunçel, “A Computational Search for Minimal Obstruction Graphs for the Lovász–Schrijver SDP Hierarchy”, arXiv:2505.24735 (2026).
Progress summary
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.