| Texto completo | |
| Autor(es): |
Berger, Soeren
[1]
;
Kohayakawa, Yoshiharu
[2]
;
Maesaka, Giulia Satiko
[1]
;
Martins, Taisa
[3]
;
Mendonca, Walner
[4]
;
Mota, Guilherme Oliveira
[2]
;
Parczyk, Olaf
[5]
Número total de Autores: 7
|
| Afiliação do(s) autor(es): | [1] Univ Hamburg, Fachbereich Math, Bundesstr 55, D-20146 Hamburg - Germany
[2] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao 1010, BR-05508090 Sao Paulo - Brazil
[3] Univ Fed Fluminense, Inst Matemat & Estat, BR-24210200 Niteroi, RJ - Brazil
[4] IMPA, Jardim Bot, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro - Brazil
[5] London Sch Econ, Dept Math, Houghton St, London WC2A 2AE - England
Número total de Afiliações: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES; v. 103, n. 4 DEC 2020. |
| Citações Web of Science: | 1 |
| Resumo | |
Given a positive integer s, 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. As a corollary, we obtain that the s-colour size-Ramsey number of n-vertex graphs with bounded treewidth and bounded degree is linear in n, which answers a question raised by Kamcev, Liebenau, Wood and Yepremyan. (AU) | |
| 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 |