Princeton Discrete Math Seminar


The Colin de Verdiere number of linklessly embeddable graphs


Laszlo Lovasz
Yale University


Fine Hall 224
Princeton University


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

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