Dr. Hein van der Holst
Dias 1,4,15 e 19 de setembro de 2000, às 14 horas
Sala 139, Bloco B, IME-USP
Abstract:
In 1990, Y. Colin de Verdière introduced a new graph parameter \mu(G), based on spectral properties of matrices associated with G. He showed that \mu(G) is monotone under taking minors and that planarity of G is characterized by the inequality \mu(G) \leq 3. In 1996, Lovász and Schrijver showed that linkless embeddability of G is characterized by the inequality \mu(G) \leq 4.
In this talk we give an overview of results on \mu(G) and of techniques to handle it, including a short proof of the above planarity characterization.