Prof. U. S. R. Murty
University of Waterloo, Canada
17 de abril de 2001, às 16 horas
Auditório Jacy Monteiro, bloco B, IME-USP
Abstract:
There is a conjecture due to Lovász and Plummer which says that there exist constants c > 0 and d > 1 such that any 2-connected cubic graph on 2n vertices has at least cd^n perfect matchings. We don't have any significant results on this question. But I shall use it to motivate some of the basic concepts in the theory of matching covered graphs.