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.

### Like this:

Like Loading...

*Related*

This entry was posted on March 22, 2007 at 5:26 pm and is filed under mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply