Title: Coberturas de grafos por estruturas multicoloridas
Data: 15 de dezembro de 2023 – terça-feira - 9h - Sala 144, Bloco B, IME/USP
Student: Antônio Kaique Barroso Fernandes

Abstract: Uma cobertura das arestas de um grafo G é um conjunto D={H_{1}, … , H_{k}} de subgrafos de G onde ∪{1 ≤ i ≤ k}E(H{i})=E(G). Se esses subgrafos são dois a dois arestas-disjuntos, dizemos que esse conjunto é uma partição das arestas. O problema de encontrar coberturas de grafos já foi estudado em suas mais diversas versões. Uma possibilidade é escolher os subgrafos procurados, e.g. caminhos, ciclos, árvores ou emparelhamentos. Outra possibilidade é determinar que esses subgrafos sejam monocromáticos (todas as arestas possuam a mesma cor) ou multicoloridos (todas as arestas possuam cores diferentes). Ademais, é possível escolher qual será o grafo hospedeiro analisado, como grafos completos, bipartidos completos, aleatórios. Neste trabalho iremos apresentar uma série de resultados para esse tipo de problema. Além disso, damos a nossa contribuição para a linha de pesquisa ao provarmos que para o grafo aleatório binomial G = G(n,p) e para todo d > 1 inteiro, se p » (\ln n)^{1/d}n^{1/d-1}, então com alta probabilidade, toda aresta-coloração própria de G admite uma cobertura de E(G) por O(n) caminhos multicoloridos.