# Colin de Verdière graph invariant

**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.^{[1]}

## Contents

## Definition[edit]

Let be a loopless simple graph. Assume without loss of generality that . Then is the largest corank of any symmetric matrix such that:

- (M1) for all with : if , and if ;
- (M2)
*M*has exactly one negative eigenvalue, of multiplicity 1; - (M3) there is no nonzero matrix such that and such that if either or hold.
^{[1]}^{[2]}

## Characterization of known graph families[edit]

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[edit]

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 .^{[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[edit]

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 Neil Robertson, Paul Seymour, and Robin Thomas (1993) of the Hadwiger conjecture for *K*_{6}-minor-free graphs.

## Other properties[edit]

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]}

Louis Esperet proved the following connection between the Colin de Verdière invariant and boxicity of the same graph:

- ,

and conjectured that the boxicity of *G* is at most the Colin de Verdière invariant of *G*.^{[6]}

## Influence[edit]

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

## Notes[edit]

- ^
^{a}^{b}^{c}^{d}^{e}^{f}^{g}^{h}^{i}^{j}van der Holst, Lovász & Schrijver (1999). - ^
^{a}^{b}^{c}^{d}^{e}^{f}Colin de Verdière (1990). **^**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.- ^
^{a}^{b}Lovász & Schrijver (1998). - ^
^{a}^{b}^{c}Kotlov, Lovász & Vempala (1997). **^**Esperet, Louis (2015). "Boxicity and Topological Invariants". arXiv:1503.05765 [math.CO].

## References[edit]

- Colin de Verdière, Yves (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, Yves (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,**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. - 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
_{6}-free graphs" (PDF),*Combinatorica*,**13**: 279–361, doi:10.1007/BF01202354.