Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40
DOI:
https://doi.org/10.35819/remat2023v9i2id6424Palavras-chave:
teoria de grafos, grafos bicoloridos, números de Ramsey, clique, conjunto independenteResumo
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.
Downloads
Referências
AZEVEDO, D. S.; MEDEIROS, J. F. de; ZITZKE, D. C.; PEREIRA, R. R.; BERNARDINO, L. S. Análise de um método de coloração no estudo do número de Ramsey R(3,10). REMAT: Revista Eletrônica da Matemática, Bento Gonçalves, RS, v. 8, n. 1, p. e3001, 2022. DOI: https://doi.org/10.35819/remat2022v8i1id4985.
CARIOLARO, D. On the Ramsey number R(3,6). Australasian Journal of Combinactorics, v. 37, p. 301-304, 2007. Disponível em: https://ajc.maths.uq.edu.au/pdf/37/ajc_v37_p301.pdf. Acesso em: 17 out. 2023.
DIESTEL, R. Graph Theory. 2. ed. eletronic edition. New York: Springer-Verlag, 2000.
EXOO, G. On Two Classical Ramsey Numbers of the Form R(3, n). SIAM Journal on Discrete Mathematics, v. 2, n. 4, p. 488-490, 1989. DOI: https://doi.org/10.1137/0402043.
GOEDGEBEUR, J.; RADZISZOWSKI, S. P. New Computational Upper Bounds for Ramsey Numbers R(3,k). Electronic Journal of Combinactorics, v. 20, n. 1, 2013. DOI: https://doi.org/10.37236/2824.
GREENWOOD, R. E.; GLEASON, A. M. Combinatorial Relations and Chromatic Graphs. Canadian Journal of Mathematics, v. 7, p. 1-7, 1955. DOI: https://doi.org/10.4153/CJM-1955-001-4.
GRINSTEAD, C. M.; ROBERTS, S. M. On the Ramsey numbers R(3,8) and R(3,9). Journal of Combinatorial Theory, v. 33, p. 27-51, 1982.
Radziszowski, S. Small Ramsey Numbers. The Electronic Journal of Combinatorics. 1994. Revisão de 2021. DOI: https://doi.org/10.37236/21.
RAMSEY, F. P. On a Problem of Formal Logic. Proceedings of the London Mathematical Society, v. 2, n. 30, p. 264-286, 1930. DOI: https://doi.org/10.1112/plms/s2-30.1.264.
SANCHES, J. Ferramentas probabilísticas aplicadas a problemas de coloração em grafos. Orientador: Carlos Hoppen. 2016. 151 f. Tese (Doutorado em Matemática Aplicada) – Universidade Federal do Rio Grande do Sul, Porto Alegre, dez. 2016. Disponível em: http://hdl.handle.net/10183/153219. Acesso em: 19 out. 2023.
SANCHES, J. Números de Ramsey em grafos multipartidos. Orientador: Emerson Luiz do Monte Carmelo. 2013. Dissertação (Mestrado em Matemática Aplicada) – Universidade Estadual de Maringá, Maringá, 2013.
SPENCER, J. H. Ramsey's Theorem: A New Lower Bound. Journal of Combinatorial Theory, Série A, v. 18, n. 1, p. 108-115, 1975. DOI: https://doi.org/10.1016/0097-3165(75)90071-0.
Downloads
Publicado
Edição
Seção
Licença
Copyright (c) 2023 REMAT: Revista Eletrônica da Matemática
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Os autores detêm os direitos autorais dos artigos publicados e concedem à REMAT o direito de primeira publicação e distribuição de partes ou do trabalho como um todo com o objetivo de promover a revista. Os autores são autorizados a distribuir a versão publicada do artigo, como por exemplo em repositórios institucionais, desde que façam menção de publicação inicial nesta revista a partir da disponibilização do DOI do artigo.
Os artigos são publicados sob a licença Creative Commons Attribution 4.0 International License (CC BY 4.0). Isso permite que o conteúdo seja utilizado para criação de novos trabalhos, tanto para fins comerciais quanto não comerciais, desde que seja feita a devida atribuição ao autor original, conforme especificado na licença.
Como Citar
https://orcid.org/0000-0002-0893-7426
