Graph decompositions and separations
Antônio Kaique Barroso Fernandes · 2024
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 [7], 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 pcom alta probabilidade, toda coloração própria das arestas de G admite uma cobertura de E(G) por O(n) caminhos multicoloridos.Em seguida, mostramos que para ε > 0 e p ≥ n ε-1 , o mesmo resultado vale.