Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters
Wayne W. Barrett, Shaun Fallat, H. Tracy Hall, Leslie Hogben · The Electronic Journal of Combinatorics · 2013
We establish the bounds $\frac 4 3 \le b_ u \le b_\xi\le \sqrt 2$, where $b_ u$ and $b_\xi$ are the Nordhaus-Gaddum sum upper bound multipliers, i.e., $ u(G)+ u(\overline{G})\le b_ u |G|$ and $\xi(G)+\xi(\overline{G})\le b_\xi | G|$ for all graphs $G$, and $ u$ and $\xi$ are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for $ u$ 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.