Show simple item record

dc.contributor.advisorHoppen, Carlospt_BR
dc.contributor.authorSchmidt, Dionatan Ricardopt_BR
dc.date.accessioned2023-06-24T03:34:49Zpt_BR
dc.date.issued2023pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/259369pt_BR
dc.description.abstractNessa tese são abordados problemas dentro da Teoria Extremal de Grafos. Mais especificamente problemas de colorações de arestas, propostos inicialmente por Erdős e Rothschild. O primeiro problema considerado aqui envolve a família de padrões P*k que não contêm o padrão arco-íris KRk . Para todo k ≥ 3, apresentamos resultados em direção a obtenção de cotas inferiores e superiores para o parâmetro r0(P*k), que é o valor onde o grafo de Turán deixa de ser o grafo extremal. Ainda em relação a família P*k , apresentamos uma construção para uma cota superior ω(P*k) em relação ao parâmetro r0(P*k), onde, para todo r ≥ ω(P*k), o grafo de Turán Tk−1(n) não é mais o grafo (r,P*k)-extremal. Outra contribuição do nosso trabalho é para k = 3, e considerando o padrão K (2) 3 da família P*3 , determinamos que o parâmetro r0(K (2) 3 ) vale 26. Mais especificamente, provamos que o grafo de Turán T2(n) é o único grafo extremal, para o padrão K (2) 3 , onde 2 ≤ r ≤ 26. A principal contribuição dessa tese é a incorporação de um componente indutivo na prova desse resultado, o que nos permite explorar melhor as restrições locais e estender o resultado de [24] para todos os valores de r para os quais foi conjecturado. Por último, aplicamos a estrutura de demonstração desenvolvida na solução do problema do parágrafo acima, obtemos progresso no melhoramento da cota inferior de r0(P*4). Conseguimos encontrar uma cota inferior µ4(P*4) que melhora a cota inferior dada pelo primeiro resultado desse trabalho, mostrando assim que essa técnica tem potencial para ser empregada para melhorar resultados já existentes.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectTeoria extremal de grafospt_BR
dc.subjectColoração de arestaspt_BR
dc.subjectGrafospt_BR
dc.titleProblemas de coloração em grafos evitando famílias de padrões de grafos completospt_BR
dc.typeTesept_BR
dc.identifier.nrb001170418pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Matemática e Estatísticapt_BR
dc.degree.programPrograma de Pós-Graduação em Matemática Aplicadapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2023pt_BR
dc.degree.leveldoutoradopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record