30 years ago, Yves Colin de Verdière introduced the algebraic graph invariant $\mu(G)$ for any undirected graph $G$, see [1]. It was motivated by the study of the second eigenvalue of certain Schrödinger operators [2,3]. It is defined in purely algebraic terms as the *maximum corank* in a set of generalized Laplacian matrices of $G$.

It turned out to be very powerful concept, linking algebraic with topological graph theory (and, by conjecture, with graph coloring). For example,

**Four Color Theorem:**Colin de Verdière conjectures $\chi(G)\leq\mu(G)+1$ where $\chi(G)$ is the chromatic number of $G$, see [4]. If true, this would prove the Four Color Theorem.**Graph minor monotone:**The property $\mu(G)\leq k$ is closed under taking graph minors of $G$, meaning $\mu(g)\leq \mu(G)$ if $g$ is a minor of $G$, see [1]. So, by the Robertson–Seymour Graph Minor Theorem, the property $\mu(G)\leq k$ can be characterized by a finite number of excluded graph minors.**Embeddability:**$\mu(G)$ characterizes this topological property for several families of graphs: embeddable in a line $(\mu\leq1)$, outerplanar $(\mu\leq2)$, planar $(\mu\leq3)$, or linklessly i.e. flat embeddable in ${\mathbb R}^3$ $(\mu\leq4)$, see [1,2].**Embeddings in more general surfaces:**If $G$ embeds in the real projective plane or in the Klein bottle, then $\mu\leq5$. If it embeds in the torus, $\mu\leq6$. If it embeds in a surface $S$ with negative Euler characteristic $\psi$, then $\mu\leq 4−2\psi$, see [4]

Now, I have two questions, the first one being the main one:

MAIN QUESTION:Is someone aware of further embeddability characterizations based on $\mu(G)$ beyond the results in bullet point No. 3? In No. 3, we have full characterizations, while the results in No. 4 are just implications for $\mu(G)$ in case $G$ can be embedded, i.e. just in one direction.

Quoting [3]:

"The parameter was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators. These operators are defined on Riemann surfaces. It turned out that in this study one can approximate the surface by a sufficiently densely embedded graph $G$, in such a way that $\mu(G)$ is the maximum multiplicity of the second eigenvalue of the operator, or a lower bound to it."

SECOND QUESTION:So it appears $\mu(G)$ was developed to resolve a problem in Schrödinger operator theory. I wondered when/how the idea emerged to study $\mu(G)$ as a graph invariant in its own right? I looked at [1] and [CV 1] but could not find an answer.

References

[1] Yves Colin de Verdiere (1990): Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Th. (B) 50, 11–21.

[2] L. Lovasz & A. Schrijver (1998): A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126, 1275–1285.

[3] H. van der Holst, L. Lovasz & A. Schrijver (1999): The Colin de Verdière graph parameter, pp. 29–
85 in: Graph Theory and Combinatorial Biology (L. Lovasz et al., eds.), János Bolyai Math.
Soc., Budapest.

[4] Andries E. Brouwer, Willem H. Haemers (2011): Spectra of graphs, Springer Monograph.

Earlier work that Colin de Verdière cites in his article [1]:

[CV 1] Y. COLIN DE VERDIÈRE, Spectres de variétés riemanniennes et spectres de graphes, Proc. Intern. Congress of Math., Berkeley 1986, 522-530.

[CV 2] Y. COLIN DE VERDIÈRE, Sur la multiplicité de la premiere valeur propre non nulle du laplacien, Comment. Math. Helv. 61 (1986), 254-270.

[CV 3] Y. COLIN DE VERDIÈRE, Sur une hypothèse de transversalité d’Arnold, Comment. Math. Helv. 63 (1988). 184-193.

[CV 4] Y. COLIN DE VERDIÈRE, Constructions de laplaciens dont une partie finie du spectre est donné, Ann. Sci. École Norm. Sup. 20 (1987), 599-615.

https://en.wikipedia.org/wiki/Colin_de_Verdi%C3%A8re_graph_invariant