# Colin de Verdière graph invariant

Colin de Verdière's invariant is a graph parameter $\mu (G)$ for any graph G, introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.

## Definition

Let $G=(V,E)$ be a simple graph with vertex set $V=\{1,\dots ,n\}$. Then $\mu (G)$ is the largest corank of any symmetric matrix $M=(M_{i,j})\in \mathbb {R} ^{(n)}$ such that:
* (M1) for all $i,j$ with $i\neq j$: $M_{i,j}<0$ if $\{i,j\}\in E$, and $M_{i,j}=0$ if $\{i,j\}\notin E$;
* (M2) $M$ has exactly one negative eigenvalue, of multiplicity 1;
* (M3) there is no nonzero matrix $X=(X_{i,j})\in \mathbb {R} ^{(n)}$ such that $MX=0$ and such that $X_{i,j}=0$ if either $i=j$ or $M_{i,j}\neq 0$ hold.

## Characterization of known graph families

Several well-known families of graphs can be characterized in terms of their Colin de Verdière invariants:
* μ ≤ 0 if and only if G has only one vertex;
* μ ≤ 1 if and only if G is a linear forest (a disjoint union of paths);
* μ ≤ 2 if and only if G is outerplanar;
* μ ≤ 3 if and only if G is planar;
* μ ≤ 4 if and only if G is linklessly embeddable in R$^3$.
These same families of graphs also show up in connections between the Colin de Verdière invariant of a graph and the structure of its complement:
* If the complement of an n-vertex graph is a linear forest, then μ ≥ n − 3;
* If the complement of an n-vertex graph is outerplanar, then μ ≥ n − 4;
* If the complement of an n-vertex graph is planar, then μ ≥ n − 5.

## Graph minors

A minor of a graph is another graph formed from it by contracting edges and by deleting edges and vertices. The Colin de Verdière invariant is minor-monotone, meaning that taking a minor of a graph can only decrease or leave unchanged its invariant:
    If H is a minor of G then $\mu (H)\leq \mu (G)$.
By the Robertson–Seymour theorem, for every k there exists a finite set H of graphs such that the graphs with invariant at most k are the same as the graphs that do not have any member of H as a minor. Colin de Verdière (1990) lists these sets of forbidden minors for k ≤ 3; for k = 4 the set of forbidden minors consists of the seven graphs in the Petersen family, due to the two characterizations of the linklessly embeddable graphs as the graphs with μ ≤ 4 and as the graphs with no Petersen family minor. For k = 5 the set of forbidden minors includes the 78 graphs of the Heawood family, and it is conjectured that this list is complete.

## Chromatic number

Colin de Verdière (1990) conjectured that any graph with Colin de Verdière invariant μ may be colored with at most μ + 1 colors. For instance, the linear forests have invariant 1, and can be 2-colored; the outerplanar graphs have invariant two, and can be 3-colored; the planar graphs have invariant 3, and (by the four color theorem) can be 4-colored.
For graphs with Colin de Verdière invariant at most four, the conjecture remains true; these are the linklessly embeddable graphs, and the fact that they have chromatic number at most five is a consequence of a proof by Neil Robertson, Paul Seymour, and Robin Thomas (1993) of the Hadwiger conjecture for K$_6$-minor-free graphs.

## Other properties

If a graph has crossing number $k$, it has Colin de Verdière invariant at most $k+3$. For instance, the two Kuratowski graphs $K_{5}$ and $K_{3,3}$ can both be drawn with a single crossing, and have Colin de Verdière invariant at most four.

## Influence

The Colin de Verdière invariant is defined through a class of matrices corresponding to the graph instead of just a single matrix. Along the same lines other graph parameters can be defined and studied, such as the minimum rank, minimum semidefinite rank and minimum skew rank.