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;[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:
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] For k = 5 the set of forbidden minors include 78 graphs of Heawood family, and it is conjectured that there are no more.[6]
If a graph has
crossing number, it has Colin de Verdière invariant at most . For instance, the two
Kuratowski graphs and can both be drawn with a single crossing, and have Colin de Verdière invariant at most four.[2]
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.
^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 or
claw minor.