Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40

Abstract

O número de Ramsey R(k,l) é o menor número inteiro n tal que não exista (k,l,n,e)-grafo, sendo que um (k,l,n,e)-grafo denota um grafo G com n vértices e e arestas e com C(G)<k e I(G)<l, onde C(G) denota o maior clique em G e I(G) denota o maior conjunto independente em G. A teoria de grafos deu origem a vastas pesquisas, pois por mais simples que seja a definição, calcular os números de Ramsey é uma tarefa árdua e poucos são conhecidos. Exoo (1989), Goedgebeur e Radziszowski (2013) mostraram que 40<= R(3,10)<= 42. Assim, neste artigo, vamos expor proposições que serão úteis no cálculo deste número de Ramsey. Baseado nas ideias de Grinstead e Roberts (1982) e Cariolaro (2007), serão exibidas propriedades e características para um grafo bicolorido de ordem 40, tal que G seja livre de triângulos, isto é, C(G)<3, e não possua conjunto independente de ordem 10, ou seja, I(G)<10. Mostraremos, por exemplo, que dado G = (V,E) um grafo de ordem 40, tal que C(G) < 3 e I(G) < 10, então, para todo vértice v em V, tem-se que 4 <= deg(v) <= 9. Por fim, ressaltamos que os resultados inéditos obtidos pelos autores, em um projeto de pesquisa desenvolvido no IFRS, Campus Alvorada, encontram-se na Seção 4.

Keywords

• teoria de grafos
• grafos bicoloridos
• números de Ramsey
• clique
• conjunto independente