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

On the local density problem for graphs of given odd-girth

Texto completo
Autor(es):
Bedenknecht, Wiebke [1] ; Mota, Guilherme Oliveira [2] ; Reiher, Christian [1] ; Schacht, Mathias [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Hamburg, Fachbereich Math, Hamburg - Germany
[2] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF GRAPH THEORY; v. 90, n. 2, p. 137-149, FEB 2019.
Citações Web of Science: 0
Resumo

Erdos conjectured that every n-vertex triangle-free graph contains a subset of left perpendicularn/2right perpendicular vertices that spans at most n(2)/50 edges. Extending a recent result of Norin and Yepremyan, we confirm this conjecture for graphs homomorphic to socalled Andrasfai graphs. As a consequence, Erdos' conjecture holds for every triangle-free graph G with minimum degree delta(G) > 10n/29 and if chi(G) <= 3 the degree condition can be relaxed to delta(G) > n/3. In fact, we obtain a more general result for graphs of higher odd-girth. (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: 13/11431-2 - Combinatória extremal e probabilística
Beneficiário:Guilherme Oliveira Mota
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/20733-2 - Combinatória extremal e probabilística
Beneficiário:Guilherme Oliveira Mota
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado