← All problems

The Graph Complement Conjecture for minimum rank

13 years old · traced to

Let GG be a graph. Write GcG^c for its complement, mr⁡(G)\operatorname{mr}(G) for the minimum rank of a real symmetric matrix described by GG, and \ordG\ord G for the number of vertices of GG.

Graph Complement Conjecture. For any graph GG,

mr⁡(G)+mr⁡(Gc)≤\ordG+2.\operatorname{mr}(G)+\operatorname{mr}(G^c)\leq \ord G+2.

This is a classical Nordhaus–Gaddum-type conjecture in minimum rank theory; the bound is sharp for paths, but the source gives no resolution in general.

References

3 papers in this index state this conjecture (2013–2025). The statement above is taken from the most recent of them; the others are arXiv:2207.07294, arXiv:1304.3751.

Source: Francesco Barioli, Shaun M. Fallat, Himanshu Gupta and Zhongshan Li, “The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture”, arXiv:2505.24577 (2025).

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.