Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

The size Ramsey number of short subdivisions of bounded degree graphs

Texto completo
Autor(es):
Kohayakawa, Yoshiharu [1] ; Retter, Troy [2] ; Rodl, Vojtech [2]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 - USA
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 54, n. 2, p. 304-339, MAR 2019.
Citações Web of Science: 2
Resumo

For graphs G and F, write G -> (F)(l) if any coloring of the edges of G with l colors yields a monochromatic copy of the graph F. Suppose S-(h) is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than (log s)(20h)s(1+1/(h+1)) edges for which G -> (S-(h))(l) holds, provided that s >= s(0)(h, d, l). Wealso extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of ``long subdivisions{''} of bounded degree graphs. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático