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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: