## Colin de Verdière invariant and Four-Color theorem

This is a follow-up to a previous post on the Colin de verdière graph invariant. I’ve come across a book in french by Colin de Verdière (Spectres de Graphes, SMF, 1998) in which he writes the following.

Let $G$ denote some graph. Then:

(a) if $G$ is embeddable in either the real projective plane $P\mathbb{R}^2$ or the Klein Bottle then $\mu(G) \leq 5$

(b) if $G$ is embeddable in the 2-torus $\mathbb{T}^2$ then $\mu(G) \leq 6$

(c) if $G$ is embeddable in a surface $S$ whose Euler characteristic $\chi(S)$ is negative then $\mu(G)\leq 4-2\chi(S)$

where (a) and (b) are “optimal”.

Moreover he states the Colin de Verdière Conjecture: for any graph we have $C(G)\leq \mu(G) +1$, where $C(G)$ is the chromatic number.

He adds that a proof of this would provide a non-computational proof of the Four-Color theorem. Moreover this conjecture is implied by Hadwiger’s conjecture, so it is weaker and thus perhaps easier to prove.