Note on Nordhaus-Gaddum problems for Colin de Verdière type parameters (Q396902)

Summary: We establish the bounds \(\frac 4 3 \leq b_\nu \leq b_\xi\leq \sqrt 2\), where \(b_\nu\) and \(b_\xi\) are the Nordhaus-Gaddum sum upper bound multipliers, i.e., \(\nu(G)+\nu(\overline{G})\leq b_\nu |G|\) and \(\xi(G)+\xi(\overline{G})\leq b_\xi | G|\) for all graphs \(G\), and \(\nu\) and \(\xi\) are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for \(\nu\) and \(\xi\) is conjectured to be \(|G| - 2\), and if these parameters are replaced by the maximum nullity \(M(G)\), this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.