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.)

Chromatic Thresholds in Sparse Random Graphs

Texto completo
Autor(es):
Allen, Peter ; Bottcher, Julia ; Griffiths, Simon ; Kohayakawa, Yoshiharu ; Morris, Robert
Número total de Autores: 5
Tipo de documento: Artigo Científico
Fonte: RANDOM STRUCTURES & ALGORITHMS; v. 51, n. 2, p. 215-236, SEP 2017.
Citações Web of Science: 1
Resumo

The chromatic threshold delta(chi) (H, p) of a graph H with respect to the random graph G(n, p) is the infimum over d > 0 such that the following holds with high probability: the family of H-free graphs G subset of G(n, p) with minimum degree delta(G) >= dpn has bounded chromatic number. The study of d. (H) := delta(chi) (H, 1) was initiated in 1973 by Erdos and Simonovits. Recently delta(chi) (H) was determined for all graphs H. It is known that delta(chi) (H, p) =delta(chi) (H) for all fixed p epsilon (0, 1), but that typically delta(chi) (H, p) epsilon not equal delta(chi) (H) if p = 0(1). Here we study the problem for sparse random graphs. We determine delta(chi) (H, p) for most functions p = p(n) when H. [K3, C5], and also for all graphs H with x(H) is not an element of [3, 4]. (C) 2017 Wiley Periodicals, Inc. (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
Processo FAPESP: 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos
Beneficiário:Julia Boettcher
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos
Beneficiário:Peter David Allen
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
Beneficiário:Jefferson Antonio Galves
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs