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. / Submitted by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T13:21:47Z
No. of bitstreams: 1
2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T13:22:11Z (GMT) No. of bitstreams: 1
2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5) / Made available in DSpace on 2016-08-01T13:22:11Z (GMT). No. of bitstreams: 1
2016_dis_alquirino.pdf: 824987 bytes, checksum: 94c4883bf8e813e23b3034b37d55820a (MD5)
Previous issue date: 2016 / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/18765 |
| Date | January 2016 |
| Creators | Quintino, Arthur Lima |
| Contributors | Benevides, Fabrício Siqueira |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds