Cobertura de grafos aleatórios por caminhos multicoloridos

  • Antônio Kaique USP
  • Guilherme O. Mota USP
  • Tássio Naia USP

Resumo


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.

Referências

Ajtai, M., Komlós, J., and Szemerédi, E. (1981). The longest path in a random graph. Combinatorica, 1:1–12.

Bonamy, M., Botler, F., Dross, F., Naia, T., and Skokan, J. (2023). Separating the edges of a graph by a linear number of paths. Preprint arXiv:2301.08707.

Janson, S., Łuczak, T., and Ruciński, A. (2000). Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York.
Publicado
06/08/2023
KAIQUE, Antônio; MOTA, Guilherme O.; NAIA, Tássio. Cobertura de grafos aleatórios por caminhos multicoloridos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 1-5. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.230768.