Número de Ramsey relativo a arestas de potências de caminhos

• Dennis Clemens
• Matthew Jenssen
• Yoshiharu Kohayakawa
• Natasha Morrison
• Guilherme Oliveira Mota
• Damian Reding
• Barnaby Roberts

DOI: https://doi.org/10.5753/etc.2017.3198

Resumo

Dados grafos G e H e um inteiro positivo q, dizemos que G é qRamsey para H se toda q-coloração das arestas de G contém uma c ópia monocromática de H. Denotamos essa propriedade por G Ñ pHqq. O nú mero de Ramsey relativo a arestas r^pHq de um grafo H é definido como r^pHq mint|EpGq| : G Ñ pHq2u. Respondendo uma pergunta sugerida por Conlon, provamos que r^pPnkq Opnq para todo k fixo, onde Pnk é a k-ésima potência do caminho com n vértices Pn, i.e., o grafo com conjunto de vértices V pPnq e todas as arestas tu; vu tais que a dist ância entre u e v em Pn é no máximo k.