Cobertura de grafos aleatórios por caminhos multicoloridos

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

DOI: https://doi.org/10.5753/etc.2023.230768

Abstract

Let G = G(n, p) be the binomial random graph. We prove that if p » (ln n/n)^1/2, then with high probability every proper edge-colouring of G admits a collection of O(n) rainbow paths which together cover E(G), where a copy of a graph is rainbow if each of its edges is coloured with a unique colour.

References

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.