| Full text | |
| Author(s): |
Bedenknecht, Wiebke
[1]
;
Mota, Guilherme Oliveira
[2]
;
Reiher, Christian
[1]
;
Schacht, Mathias
[1]
Total Authors: 4
|
| Affiliation: | [1] Univ Hamburg, Fachbereich Math, Hamburg - Germany
[2] Univ Fed ABC, Ctr Matemat Comp & Cognicao, Santo Andre - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | JOURNAL OF GRAPH THEORY; v. 90, n. 2, p. 137-149, FEB 2019. |
| Web of Science Citations: | 0 |
| Abstract | |
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) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 13/11431-2 - Extremal and probabilistic combinatorics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/20733-2 - Extremal and probabilistic combinatorics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Scholarships abroad - Research Internship - Post-doctor |