Minimal Ramsey-constrained trees

• 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

Abstract

Given graphs G, S and H, we write G mr-arrows (S,H) if every edge-colouring of G contains a monochromatic copy of S or a rainbow copy of H. We prove that, for S = K_{1,3} and H a complete binary tree of height h, the smallest tree T that mr-arrows (S,H) has size 2^{(1/2+o(1))h^2}.

Keywords: Ramsey theory, constrained colourings, rainbow trees

References

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.