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 loopless simple graph. Assume without loss of generality that $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 no edges;
• μ ≤ 1 if and only if G is a linear forest (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 graph

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;
• 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.

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 Robertson, Seymour & Thomas (1993) of the Hadwiger conjecture for K₆-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₅ and K_3,3 can both be drawn with a single crossing, and have Colin de Verdière invariant at most four.

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 line 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.

References

• Colin de Verdière, Y. (1990), "Sur un nouvel invariant des graphes et un critère de planarité", Journal of Combinatorial Theory, Series B, 50 (1): 11–21, doi:10.1016/0095-8956(90)90093-F. Translated by Neil Calkin as Colin de Verdière, Y. (1993), "On a new graph invariant and a criterion for planarity", in Robertson, Neil; Seymour, Paul (eds.), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 137–147.
• van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999), "The Colin de Verdière graph parameter", Graph Theory and Combinatorial Biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud., vol. 7, Budapest: János Bolyai Math. Soc., pp. 29–85.
• Kotlov, Andrew; Lovász, László; Vempala, Santosh (1997), "The Colin de Verdiere number and sphere representations of a graph", Combinatorica, 17 (4): 483–521, doi:10.1007/BF01195002
• Lovász, László; Schrijver, Alexander (1998), "A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs", Proceedings of the American Mathematical Society, 126 (5): 1275–1285, doi:10.1090/S0002-9939-98-04244-0.
• Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwiger's conjecture for K₆-free graphs" (PDF), Combinatorica, 13: 279–361, doi:10.1007/BF01202354.