Колин де Вердьер инварианты және графиктердің қасиеттері

Graph property
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. μ ≤ 2 if and only if G is outerplanar;
μ ≤ 4 if and only if G is linklessly embeddable in R3. 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;

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 of the Hadwiger conjecture for K6 minor free graphs.

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.

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.