The enumeration conjecture for 3-minimal graphs

From papers

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 4949 non-isomorphic 33-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.

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

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).

Solutions 0

No solutions have been posted yet.