Colin de Verdière graph invariant

Graph property

Colin de Verdière's invariant is a graph parameter  μ ( G ) {\displaystyle \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.[1]

## Definition

[edit]

Let  G = ( V , E ) {\displaystyle G=(V,E)} be a simple graph with vertex set  V = { 1 , … , n } {\displaystyle V=\\{1,\dots ,n\\}} . Then  μ ( G ) {\displaystyle \mu (G)} is the largest corank of any symmetric matrix M = ( M i , j ) ∈ R ( n ) {\displaystyle M=(M_{i,j})\in \mathbb {R} ^{(n)}} such that:

* (M1) for all  i , j {\displaystyle i,j} with  i ≠ j {\displaystyle i\neq j} :  M i , j < 0 {\displaystyle M_{i,j}<0} if  { i , j } ∈ E {\displaystyle \\{i,j\\}\in E} , and  M i , j = 0 {\displaystyle M_{i,j}=0} if  { i , j } ∉ E {\displaystyle \\{i,j\\}\notin E} ;
* (M2)  M {\displaystyle M} has exactly one negative eigenvalue, of multiplicity 1;
* (M3) there is no nonzero matrix  X = ( X i , j ) ∈ R ( n ) {\displaystyle X=(X_{i,j})\in \mathbb {R} ^{(n)}} such that  M X = 0 {\displaystyle MX=0} and such that  X i , j = 0 {\displaystyle X_{i,j}=0} if either  i = j {\displaystyle i=j} or  M i , j ≠ 0 {\displaystyle M_{i,j}\neq 0} 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 only one vertex;[1][2]
* μ ≤ 1 if and only if G is a linear forest (a 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 in R3.[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:

* 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  μ ( H ) ≤ μ ( G ) {\displaystyle \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] 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]

## 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 K6-minor-free graphs.

## Other properties

[edit]

If a graph has crossing number k {\displaystyle k} , it has Colin de Verdière invariant at most  k + 3 {\displaystyle k+3} . For instance, the two Kuratowski graphs  K 5 {\displaystyle K_{5}} and  K 3 , 3 {\displaystyle K_{3,3}} can both be drawn with a single crossing, and have Colin de Verdière invariant at most four.[2]

## Influence

[edit]

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.

## Notes

[edit]

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 or claw minor.
4. ^ a b Lovász & Schrijver (1998).
5. ^ a b c Kotlov, Lovász & Vempala (1997).
6. ^ Hein van der Holst (2006). "Graphs and obstructions in four dimensions" (PDF). Journal of Combinatorial Theory, Series B. 96 (3): 388–404\. doi:10.1016/j.jctb.2005.09.004.388-404&rft.date=2006&rft_id=info:doi/10.1016/j.jctb.2005.09.004&rft.au=Hein+van+der+Holst&rft_id=https://core.ac.uk/download/pdf/82523665.pdf&rfr_id=info:sid/en.wikipedia.org:Colin+de+Verdière+graph+invariant" class="Z3988">

## 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-F11-21&rft.date=1990&rft_id=info:doi/10.1016/0095-8956(90)90093-F&rft.aulast=Colin+de+Verdière&rft.aufirst=Yves&rfr_id=info:sid/en.wikipedia.org:Colin+de+Verdière+graph+invariant" class="Z3988">. Translated by Neil J. 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, vol. 147, American Mathematical Society, pp. 137–147137-147&rft.pub=American+Mathematical+Society&rft.date=1993&rft.aulast=Colin+de+Verdière&rft.aufirst=Yves&rfr_id=info:sid/en.wikipedia.org:Colin+de+Verdière+graph+invariant" class="Z3988">.
* 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, archived from the original on 2016-03-03, retrieved 2010-08-0629-85&rft.pub=János+Bolyai+Math.+Soc.&rft.date=1999&rft.aulast=van+der+Holst&rft.aufirst=Hein&rft.au=Lovász,+László&rft.au=Schrijver,+Alexander&rft_id=http://www.cs.elte.hu/~lovasz/colinsurv.ps&rfr_id=info:sid/en.wikipedia.org:Colin+de+Verdière+graph+invariant" class="Z3988">.
* 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, archived from the original on 2016-03-03, retrieved 2010-08-06483-521&rft.date=1997&rft_id=info:doi/10.1007/BF01195002&rft.aulast=Kotlov&rft.aufirst=Andrew&rft.au=Lovász,+László&rft.au=Vempala,+Santosh&rft_id=http://oldwww.cs.elte.hu/~lovasz/sphere.ps&rfr_id=info:sid/en.wikipedia.org:Colin+de+Verdière+graph+invariant" class="Z3988">
* 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-01275-1285&rft.date=1998&rft_id=info:doi/10.1090/S0002-9939-98-04244-0&rft.aulast=Lovász&rft.aufirst=László&rft.au=Schrijver,+Alexander&rfr_id=info:sid/en.wikipedia.org:Colin+de+Verdière+graph+invariant" class="Z3988">.
* Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwiger's conjecture for K6-free graphs" (PDF), Combinatorica, 13 (3): 279–361, doi:10.1007/BF01202354, archived from the original (PDF) on 2009-04-10, retrieved 2010-08-06279-361&rft.date=1993&rft_id=info:doi/10.1007/BF01202354&rft.aulast=Robertson&rft.aufirst=Neil&rft.au=Seymour,+Paul&rft.au=Thomas,+Robin&rft_id=http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf&rfr_id=info:sid/en.wikipedia.org:Colin+de+Verdière+graph+invariant" class="Z3988">.