Colin de Verdière's invariant is a graph parameter
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.
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 includes the 78 graphs of the Heawood family, and it is conjectured that this list is complete.
[6] Colin de Verdière (1990) conjectured that any graph with Colin de Verdière invariant μ may be colored with at most μ + 1 colors.
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.
can both be drawn with a single crossing, and have Colin de Verdière invariant at most four.
[2] The Colin de Verdière invariant is defined through a class of matrices corresponding to the graph instead of just a single matrix.