Cobertura de grafos aleatórios por caminhos multicoloridos
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.
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
Como Citar
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.
