| Texto completo | |
| Autor(es): |
Stein, Maya
;
Zarate-Gueren, Camila
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | PROCEEDINGS OF THE 12TH EUROPEAN CONFERENCE ON COMBINATORICS, GRAPH THEORY AND APPLICATIONS, EUROCOMB 2023; v. N/A, p. 7-pg., 2023-01-01. |
| Resumo | |
An oriented graph is called antidirected if it has no directed path with 2 edges. We prove that asymptotically, any oriented graph D of minimum semidegree greater than k/2 contains every balanced antidirected tree of bounded degree and with k edges, and D also contains every antidirected subdivision H of a sufficiently small complete graph K-h, with a mild restriction on the lengths of the antidirected paths in H replacing the edges of K-h, and with H having a total of k edges. Further, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomasse stating that every digraph on n vertices and with more than (k- 1)(n) edges contains all antidirected trees with k edges. We show that their conjecture is asymptotically true in oriented graphs for balanced antidirected trees of bounded degree and size linear in n. (AU) | |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |