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 denote some graph. Then:
(a) if is embeddable in either the real projective plane or the Klein Bottle then
(b) if is embeddable in the 2-torus then
(c) if is embeddable in a surface whose Euler characteristic is negative then
where (a) and (b) are “optimal”.
Moreover he states the Colin de Verdière Conjecture: for any graph we have , where 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.