# Colin de Verdière graph invariant

Colin de Verdière's invariant is a graph parameter ${\displaystyle \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.[1]

## Definition

Let ${\displaystyle G=(V,E)}$ be a loopless simple graph. Assume without loss of generality that ${\displaystyle V=\{1,\dots ,n\}}$. Then ${\displaystyle \mu (G)}$ is the largest corank of any symmetric matrix ${\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)}}$ such that:

• (M1) for all ${\displaystyle i,j}$ with ${\displaystyle i\neq j}$: ${\displaystyle M_{i,j}<0}$ if ${\displaystyle \{i,j\}\in E}$, and ${\displaystyle M_{i,j}=0}$ if ${\displaystyle \{i,j\}\notin E}$;
• (M2) M has exactly one negative eigenvalue, of multiplicity 1;
• (M3) there is no nonzero matrix ${\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)}}$ such that ${\displaystyle MX=0}$ and such that ${\displaystyle X_{i,j}=0}$ if either ${\displaystyle i=j}$ or ${\displaystyle M_{i,j}\neq 0}$ hold.[1][2]

## Characterization of known graph families

Several well-known families of graphs can be characterized in terms of their Colin de Verdière invariants:

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 graph:

• If the complement of an n-vertex graph is a linear forest, then μ ≥ n − 3;[1][5]
• If the complement of an n-vertex graph is outerplanar, then μ ≥ n − 4;[1][5]
• If the complement of an n-vertex graph is planar, then μ ≥ n − 5.[1][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 ${\displaystyle \mu (H)\leq \mu (G)}$.[2]

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.[4]

## 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 K6-minor-free graphs.

## Other properties

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

Louis Esperet proved the following connection between the Colin de Verdière invariant and boxicity of the same graph:

${\displaystyle \operatorname {box} (G)=O(\mu (G)^{4}(\log(\mu (G))^{2})}$,

and conjectured that the boxicity of G is at most the Colin de Verdière invariant of G.[6]

## Influence

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

## Notes

1. ^ Colin de Verdière (1990) does not state this case explicitly, but it follows from his characterization of these graphs as the graphs with no triangle graph or claw minor.
2. ^ a b
3. ^ a b c
4. ^ Esperet, Louis (2015). "Boxicity and Topological Invariants". arXiv:1503.05765 [math.CO].