Please use this identifier to cite or link to this item: http://repositorio.ufc.br/handle/riufc/18765
Type: Dissertação
Title: Vértice-particionamentos de grafos aresta-coloridos em caminhos e ciclos monocromáticos
Title in English: Vertex-partitioning edge-colored graphs on paths and monochrome cycles
Authors: Quintino, Arthur Lima
Advisor: Benevides, Fabrício Siqueira
Keywords: Partições de vértices;Colorações de arestas;Grafos multipartidos completos
Issue Date: 2016
Citation: QUINTINO, 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.
Abstract in Brazilian Portuguese: Em 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.
Abstract: In 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.
URI: http://www.repositorio.ufc.br/handle/riufc/18765
Appears in Collections:DMAT - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2016_dis_alquirino.pdf805,65 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.