Vértice-particionamentos de grafos aresta-coloridos em caminhos e ciclos monocromáticos

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.