THE SIZE-RAMSEY NUMBER OF POWERS OF BOUNDED DEGREE TREES

Author(s)

Berger, S. ^[1] ; Kohayakawa, Y. ^[2] ; Maesaka, G. S. ^[1] ; Martins, T. ^[3] ; Mendonca, W. ^[3] ; Mota, G. O. ^[4] ; Parczyk, O. ^[5]

Affiliation

^[1] Univ Hamburg, Fachbereich Math, Hamburg - Germany

^[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil

^[3] IMPA, Jardim Bot, Rio De Janeiro - Brazil

^[4] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre - Brazil

^[5] Tech Univ Ilmenau, Inst Math, Ilmenau - Germany

• Document type: Journal article
• Source: ACTA MATHEMATICA UNIVERSITATIS COMENIANAE; v. 88, n. 3, p. 451-456, 2019.
• Web of Science Citations: 0

Abstract

Given an integer s >= 1, the s-colour size-Ramsey number of a graph H is the smallest integer m such that there exists a graph G with m edges with the property that, in any colouring of E (G) with s colours, there is a monochromatic copy of H. We prove that, for any positive integers k and s, the s-colour size-Ramsey number of the kth power of any n-vertex bounded degree tree is linear in n. (AU)

• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Research Grants - Young Investigators Grants