Colin de Verdière graph invariant

Definition

Let G=(V,E) be a simple graph with vertex set 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} 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:

• μ = −1 if and only if G is the order-zero graph, K;
• μ ≤ 0 if and only if G has no more than one vertex;
• μ ≤ 1 if and only if G is a linear forest (a 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 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;
• 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. lists these sets of forbidden minors for k ≤ 3 (although the sole forbidden minor for k = 0 would be rather than K if graphs are not assumed to be connected as they were in that paper); 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. 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.

Chromatic number

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.

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_5 and K_{3,3} can both be drawn with a single crossing, and have Colin de Verdière invariant at most four.

Influence

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

References

• {{citation | editor1-last = Robertson | editor1-first = Neil | editor1-link = Neil Robertson (mathematician) | editor2-last = Seymour | editor2-first = Paul | editor2-link = Paul Seymour (mathematician)
• {{citation | author2-link = László Lovász | author3-link = Alexander Schrijver | access-date = 2010-08-06 | archive-date = 2016-03-03 | archive-url = https://web.archive.org/web/20160303165118/http://www.cs.elte.hu/~lovasz/colinsurv.ps | url-status = dead
• {{citation | author2-link = László Lovász | access-date = 2010-08-06 | archive-date = 2016-03-03 | archive-url = https://web.archive.org/web/20160303190340/http://oldwww.cs.elte.hu/~lovasz/sphere.ps | url-status = dead
• {{citation
• .

References

1. {{harvtxt. van der Holst. Lovász. Schrijver. 1999.
2. {{harvtxt. 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. triangle]] or [[claw (graph theory). claw]] minor.
3. {{harvtxt. Colin de Verdière. 1990.
4. {{harvtxt. Lovász. Schrijver. 1998.
5. {{harvtxt. Kotlov. Lovász. Vempala. 1997.
6. Hein van der Holst. (2006). "Graphs and obstructions in four dimensions". Journal of Combinatorial Theory, Series B.