Cobertura de grafos aleatórios por caminhos multicoloridos - Kaique, Antônio; Mota, Guilherme O.; Naia, Tássio (Anais do Encontro de Teoria da Computação (ETC); 2023: Anais do VIII Encontro de Teoria da Computação, 2023)
Seja G = G(n, p) o grafo aleatório binomial. Provamos que se p » (ln n/n) 1/2 , então com alta probabilidade toda aresta-coloração própria de G admite uma cobertura de E(G) por O(n) caminhos multicoloridos, em que uma cópia de um grafo é dita multicolorida se todas as suas arestas possuem cores distintas.