## The Colin de Verdière graph invariant

A very interesting open problem in topology and combinatorics is to find out, for some given $k\in\mathbb{N}$, what the inequality $\mu(G)\leq k$ for a graph $G$ means, and in fact if it does mean anything at all for large $k$. Here $\mu$ is the Colin de Verdière graph invariant, a minor-monotone invariant of spectral origin.

Known results are:

• $\mu(G)\leq 1$ iff $G$ is a disjoint union of paths;
• $\mu(G)\leq 2$ iff $G$ is outerplanar;
• $\mu(G)\leq 3$ iff $G$ is planar;
• $\mu(G)\leq 4$ iff $G$ is linklessly embeddable.

That’s very neat indeed! Unfortunately even guessing what it means for $k=5$ seems pretty hard. What is the next step after being planar and having no links ? Having only one connected component ? Or maybe having no cycle ? (Update: actually these two last ideas obviously wouldn’t work since they both imply linkless embeddability. Sigh.)

### 5 Responses to “The Colin de Verdière graph invariant”

1. sirix Says:

And what does linklessly embeddable mean?

2. thomas1111 Says:

See this for the definition of a link.

3. sirix Says:

I knew what is link, wanted to know where it’s embeddable 🙂 But I guess it’s R^3 which somehow I coudn’t figure out yesterday 🙂

4. thomas1111 Says:

Yes, it’s $\mathbb{R}^3$ as usual for knot theory, see the paper by Lovász and Schrijver here 😉

5. Colin de Verdière invarariant and Four-Color theorem « Azur, sciences & arts Says:

[…] de Verdière invarariant 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 […]