Colin de Verdière graph invariant

Colin de Verdière's invariant is a graph parameter μ(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 G = (V,E) be a loopless simple graph. Assume without loss of generality that $V=\{1,\dots,n\}$. Then μ(G) is the largest corank of any 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 and j are adjacent, and M_i,j = 0 if i and j are nonadjacent;
• (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 whenever i = j or $M_{i,j}\neq 0$.^[2][1]

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][2]
• μ ≤ 1 if and only if G is a linear forest (disjoint union of paths);^[1][3]
• μ ≤ 2 if and only if G is outerplanar;^[1][2]
• μ ≤ 3 if and only if G is planar;^[1][2]
• μ ≤ 4 if and only if G is linklessly embeddable graph^[1][4]

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 $\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 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.^[2]

Notes

1. ^ ^{a b c d e f g h i j} van der Holst, Lovász & Schrijver (1999).
2. ^ ^{a b c d e f} Colin de Verdière (1990).
3. ^ 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.
4. ^ ^{a b} Lovász & Schrijver (1998).
5. ^ ^{a b c} Kotlov, Lovász & Vempala (1997).

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, Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics, 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., 7, Budapest: János Bolyai Math. Soc., pp. 29–85, http://www.cs.elte.hu/~lovasz/colinsurv.ps .
• 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, http://oldwww.cs.elte.hu/~lovasz/sphere.ps 
• 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", Combinatorica 13: 279–361, doi:10.1007/BF01202354, http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf .