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 […]

Leave a Reply

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

You are commenting using your 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: