THE SIZE-RAMSEY NUMBER OF POWERS OF BOUNDED DEGREE TREES

Autor(es)

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

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: ACTA MATHEMATICA UNIVERSITATIS COMENIANAE; v. 88, n. 3, p. 451-456, 2019.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores