Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/18765
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorBenevides, Fabrício Siqueira-
dc.contributor.authorQuintino, Arthur Lima-
dc.date.accessioned2016-08-01T13:22:11Z-
dc.date.available2016-08-01T13:22:11Z-
dc.date.issued2016-
dc.identifier.citationQUINTINO, Arthur Lima. Vértice-particionamentos de grafos aresta-coloridos em caminhos e ciclos monocromáticos. 2016. 59 f. Dissertação (Mestrado em Matemática)- Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2016.-
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/18765-
dc.description.abstractIn 1989, Gyárfás conjectured that, for every natural r, r monochromatic paths are suficient to vertex-partition any r-edge-coloured complete graph. Later, Erdos, Gyárfás and Pyber proposed a stronger version of this conjecture, in which r monochromatic cycles are wanted instead of r monochromatic paths. In this dissertation, we present many problems and results related to such conjectures, including problems where the graph to be coloured is not a complete graph, but a complete multipartite graph. We also highlight how the Szemeredi's regularity lemma may be applied in this context. Furthermore, we prove two original results. In the first one, we extend some arguments introduced by Gyárfás and Lehel in order to obtain an alternative, simpler, proof for a result due to Pokrovskiy. Whereas in the second, we show that 4 monochromatic cycles are suficient to vertex-partition any 2-edge-coloured balanced complete bipartite graph, thereby reducing the number of 12 monochromatic cycles that had been previously obtained by Schaudt and Stein. Lastly, we discuss some strategies that may be followed in future works in order to reduce the quantity of monochromatic cycles needed in this case from 4 to 3, which is the minimum possible for such case.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectPartições de vérticespt_BR
dc.subjectColorações de arestaspt_BR
dc.subjectGrafos multipartidos completospt_BR
dc.titleVértice-particionamentos de grafos aresta-coloridos em caminhos e ciclos monocromáticospt_BR
dc.typeDissertaçãopt_BR
dc.description.abstract-ptbrEm 1989, Gyárfás conjecturou que, para todo r natural, r caminhos monocromáticos são suficientes para vértice-particionar qualquer grafo completo r-aresta-colorido. Mais tarde, Erdos, Gyárfás e Pyber propuseram uma versão mais forte dessa conjectura, na qual r ciclos monocromáticos são procurados em vez de r caminhos monocromáticos. Nesta dissertação, apresentamos vários problemas e resultados relacionados com tais conjecturas, incluindo problemas onde o grafo a ser colorido não é um grafo completo, mas sim um grafo multipartido completo. Destacamos ainda como o Lema da regularidade de Szemerédi pode ser aplicado nesse contexto. Al em disso, provamos dois resultados originais. No primeiro deles, estendemos alguns argumentos introduzidos por Gyárfás e Lehel afim de obtermos uma prova alternativa, mais simples, para um resultado devido a Pokrovskiy. Enquanto que no segundo, mostramos que 4 ciclos monocromáticos são suficientes para vértice-particionar qualquer grafo bipartido completo balanceado 2-aresta-colorido, reduzindo assim o número de 12 ciclos monocromáticos que havia sido obtido anteriormente por Schaudt e Stein. Por fim, discutimos algumas estratégias que podem ser seguidas em trabalhos futuros a fim de reduzir a quantidade de ciclos monocromáticos necessários nesse caso de 4 para 3, o que e o mínimo possível para tal caso.pt_BR
dc.title.enVertex-partitioning edge-colored graphs on paths and monochrome cyclespt_BR
Aparece nas coleções:DMAT - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2016_dis_alquirino.pdf805,65 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.