Data: 21/10/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Minimizando comprimentos distintos em modelos de grafos de intervalo
Palestrante: Fabiano Oliveira (UERJ)

Resumo: Um grafo G é de intervalo se existe uma família de intervalos da reta real, cada intervalo correspondendo a um vértice de G, de modo que (u,v) é uma aresta de G se e somente se a interseção dos intervalos correspondentes aos vértices u e v é não vazia. Tal família, se existente, é chamada de modelo de G. Um grafo de intervalo é unitário se há um modelo associado no qual todos os intervalos têm comprimento unitário.

Dado um grafo de intervalo G, dizemos que G possui contagem de intervalo k se existe um modelo associado a G que empregue no máximo k comprimentos distintos de intervalo. Embora tanto grafos de intervalo quanto grafos de intervalo unitário sejam muito bem conhecidos, com centenas de artigos sobre eles, problemas associados a grafos com contagem de intervalo k, para qualquer k >= 2, são pouco explorados na literatura. Em particular, a complexidade do problema de reconhecer se um grafo possui contagem de intervalo k é um problema em aberto desde a década de 80, quando foi sugerido por Ronald Graham.

Nesse trabalho, apresentaremos uma visão geral do problema, principais resultados encontrados na literatura, incluindo avanços recentes.