Árvores Ramsey-restritas mínimas

• Maurício Collares UFMG http://orcid.org/0000-0001-5856-611X
• Antônio K. B. Fernandes UFMG
• Guilherme O. Mota USP https://orcid.org/0000-0001-9722-1819
• Hugo M. Vicente UFMG

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

Resumo

Para grafos G, S e H, dizemos que G mr-flecha (S,H) se toda coloração das arestas de G tem uma cópia monocromática de S ou uma cópia multicolorida de H. Provamos que se S = K_{1,3} e H é uma árvore binária completa de altura h, então o tamanho da menor árvore T que mr-flecha(S,H) é 2^{(1/2+o(1))h^2}.

Palavras-chave: teoria de Ramsey, colorações restritas, árvores multicoloridas

Referências

Alon, N., Jiang, T., Miller, Z., and Pritikin, D. (2003). Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints. Random Structures & Algorithms, 23(4):409–433.

Collares, M., Kohayakawa, Y., Moreira, C. G., and Mota, G. O. (2021). Constrained colourings of random graphs. Procedia Computer Science. To appear.

Gyárfás, A., Lehel, J., and Schelp, R. H. (2007). Finding a monochromatic subgraph or arainbow path. Journal of Graph Theory, 54(1):1–12.

Jamison, R. E., Jiang, T., and Ling, A. C. (2003). Constrained ramsey numbers of graphs. Journal of Graph Theory, 42(1):1–16.

Loh, P.-S. and Sudakov, B. (2009). Constrained ramsey numbers. Combinatorics, Probability and Computing, 18(1-2):247–258.