Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2014.tde-20230727-113457
Documento
Autor
Nome completo
Paulo Victor Teixeira Eufrásio
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2014
Orientador
Título em português
Pares Ramsey infinitos
Palavras-chave em português
Teoria Dos Grafos
Resumo em português
Dados grafos F, G e H, dizemos que F flecha (G, H) e denotamos por F 2192 (G, H) a propriedade de F de possuir, em toda coloração de suas arestas com duas cores, digamos vermelha e azul, uma cópia vermelha de G ou uma cópia azul de H. Um par de grafos (G, H) é dito Ramsey infinito (finito) se existe uma quantidade infinita (finita) de grafos F que são minimais com respeito a propriedade F 2192 (G, H), ou seja, grafos que flecham (G, H) cujos subgrafos próprios não flecham. Nesta dissertação, mostramos que se G é um grafo com grau mÃnimo 2 e cintura g satis- fazendo m2(G) = (g 2212 1)/(g 2212 2) e H um grafo 2-conexo que não contém circuito induzido de comprimento maior do que ou igual a g, então o par (G, H) é Ramsey infinito.
Título em inglês
Ramsey minimal pairs of graphs
Resumo em inglês
Given graphs F, G and H, we write F 2192 (G, H) to mean that any colouring of the edges of F with two colors, say red and blue, contains a red copy of G or a blue copy of H. A pair of graphs (G, H) is said to be Ramsey-infnite (finite) if there are infinitely many minimal graphs F for which we have F 2192 (G, H), i.e. graphs that are Ramsey for (G, H) whose proper subgraphs are not. We show that if G is a graph with minimum degree 2 and girth g satisfying m2(G) = (g 22121)/(g 22122) and H is 2-connected graph that contains no induced cycles of length at least g, then the pair (G, H) is Ramsey-infinite.
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2023-07-27