Limiares cromáticos de grafos
Limiares cromáticos de grafos
Expositor: Rob Morris
Instituição: IMPA
Data e Horário: 21/08/2018 | 17h:30min


RESUMO
:Um teorema antigo e famoso de Erdos afirma que, para qualquer grafo H com ciclos, existem grafos H-livres com número cromático arbitrariamente grande, isso é, não é possível colorir os vértices com um número limitado de cores sem criar uma aresta monocromática. Os grafos de Erdos eram esparsos, e então Erdos e Simonovits perguntaram, em 1973, se existem grafos densos com as mesmas propriedades. Nessa palestra, tentaremos dar uma resposta a essa pergunta.

Carregando