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