Sobre o Número de Overlap em Grafos

Para todo grafo podemos associar uma família de conjuntos de forma que cada vértice do grafo está associado a um conjunto da família e que, para toda aresta do grafo, os conjuntos associados ao par de vértices possuem interseção não vazia e não estão contidos um no outro. A esta relação entre um par de conjuntos chamamos de relação de overlap e esta família de conjuntos é chamada representação overlap.
O número de overlap de um grafo é o tamanho do menor conjunto-base possível de uma representação overlap do grafo. Neste trabalho fazemos um estudo sobre o problema Número de Overlap de grafos, apresentando resultados já existentes na literatura, como o valor extremal do número de overlap de um grafo e limites do número de overlap de um grafo a partir de suas propriedades, como número de arestas e conjunto estável máximo.
Restringindo o problema, conseguimos determinar resultados exatos ou limites superiores do número de overlap para grafos de classes específicas. Apresentamos inicialmente resultados conhecidos na literatura para algumas classes. Em seguida apresentamos nossos resultados: um aprimoramento do limite superior do número de overlap para grafos cordais e de intervalo, estabelecimento de um limite superior do número de overlap de grafos de limiar e uma representação overlap ótima dos grafos cadeia.