Bernd Kreuter (kreuter@informatik.hu-berlin.de)
Institut fuer Informatik
Humboldt Universitaet zu Berlin
Sexta-feira, 22 de agosto de 1997, 14:00
Sala 242, Bloco A, IME-USP
Abstract: In this talk, we consider several problems such as Hamiltonian Circuit and Graph Colouring on graphs $G$ of bounded maximum degree and large girth. We will show that in a graph $G$ having no cycles of length up to $|G|^{1/2}$, the Hamiltonian Circuit can be decided in polynomial time. On the other hand, this problem remains NP-complete on the class of graphs of girth at least $|G|^{1/2-\epsilon}$ for any $\epsilon>0$.
We mention several related results for other problems on graphs.
(Joint work with Th. Emden-Weinert and S. Hougardy.)