| Full text | |
| Author(s): |
Naia, Tassio
Total Authors: 1
|
| Document type: | Journal article |
| Source: | ELECTRONIC JOURNAL OF COMBINATORICS; v. 29, n. 2, p. 5-pg., 2022-05-06. |
| Abstract | |
For every graph G, let t(G) denote the largest integer t such that every oriented tree of order t appears in every orientation of G. In 1980, Burr conjectured that t(G) > 1 + ??(G)/2 for all G, and showed that t(G) > 1 + L ??(G)]; this bound remains the state of the art, apart from the multiplicative constant. We present an elementary argument that improves this bound whenever G has somewhat large chromatic number, showing that t(G) > L??(G)/ log2 v(G)] for all G. (AU) | |
| FAPESP's process: | 19/04375-5 - Problems in Ramsey Theory, random graphs and embeddings |
| Grantee: | Tássio Naia dos Santos |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Research Grants - Young Investigators Grants |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research Grants |