# Princeton Discrete Math Seminar

## Title:

The Colin de Verdiere number of linklessly embeddable graphs

## Speaker:

- Laszlo Lovasz
- Yale University

## Place:

- Fine Hall 224
- Princeton University

## Time:

- 2:30 p.m.
- Wednesday, April 30, 1997

Abstract:
Y. Colin de Verdiere introduced a new graph parameter based on spectral
properties of matrices associated with the graph. He showed that this
parameter is monotone under taking minors and that planar graphs are
exactly those with parameter value at most 3.

It was conjectured by Robertson, Seymour and Thomas and proved recently
by Lovasz and Schrijver that the parameter is at most 4 if and only if
the graph is linklessly embeddable in 3-space.

A key ingredient of the proof is a Borsuk-type theorem on the existence
of a pair of antipodal 2-faces of a 5-polytope whose boundaries are
linked in a given embedding of the 1-skeleton in 3-space.

Document last modified on April 25, 1997