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

Autor(es)

Bedenknecht, Wiebke ^[1] ; Mota, Guilherme Oliveira ^[2] ; Reiher, Christian ^[1] ; Schacht, Mathias ^[1]

Afiliação do(s) autor(es)

^[1] Univ Hamburg, Fachbereich Math, Hamburg - Germany

^[2] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre - Brazil

• 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
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/11431-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 13/20733-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado