Dissertação de Mestrado

This masters thesis primarily aims to present the problem of separating sets, with a focus on the problem proposed by Katona of finding the size of the smallest separating system of the edges of a graph using paths. The text outlines the history of the problem, as well as the proof presented by Bonamy, Botler, Dross, Naia, and Skokan, which showed that every graph admits a separating path system of linear size in the number of vertices. Additionally, we provide a brief history of graph covering problems and present original results developed during the research period of the masters program. Initially, we prove that for p \\gg (\\log n)^{1/2}/n the binomial random graph G=G(n,p), with high probability, any proper edge-coloring of G admits a covering of E(G) by \\bigoh(n) multicolored paths. Subsequently, we show that for \\varepsilon > 0 and p \\geq n^{\\varepsilon - 1}, the same result holds.

Esta dissertação de mestrado tem como objetivo principal apresentar o problema de conjuntos separadores, com foco no problema proposto por Katona de encontrar o tamanho do menor sistema separador das arestas de um grafo por caminhos. O texto apresenta a história do problema, bem como a prova apresentada por Bonamy, Botler, Dross, Naia e Skokan, que mostrou que todo grafo admite um sistema de caminhos separadores de tamanho linear no número de vértices. Ademais, apresentamos uma breve história dos problemas de coberturas em grafos e apresentamos resultados autorais desenvolvidos durante o período de pesquisa no mestrado. Inicialmente, provamos que, para p\\gg (\\log n)^{1/2}/n o grafo aleatório binomial G=G(n,p), com alta probabilidade, toda coloração própria das arestas de G admite uma cobertura de E(G) por \\bigoh(n) caminhos multicoloridos. Em seguida, mostramos que para \\varepsilon > 0 e p \\geq n^{\\varepsilon - 1}, o mesmo resultado vale.