Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters

Abstract

We establish the bounds $\frac 4 3 \le b_\nu \le b_\xi\le \sqrt 2$, where $b_\nu$ and $b_\xi$ are  the Nordhaus-Gaddum sum upper bound multipliers, i.e., $\nu(G)+\nu(\overline{G})\le b_\nu |G|$ and $\xi(G)+\xi(\overline{G})\le 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.