Triangle packings and 1-factors in oriented graphs
| dc.creator | Keevash, Peter | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2008-06-12 | |
| dc.date.accessioned | 2026-07-07T09:44:09Z | |
| dc.date.available | 2026-07-07T09:44:09Z | |
| dc.description | An oriented graph is a directed graph which can be obtained from a simple undirected graph by orienting its edges. In this paper we show that any oriented graph G on n vertices with minimum indegree and outdegree at least (1/2-o(1))n contains a packing of cyclic triangles covering all but at most 3 vertices. This almost answers a question of Cuckler and Yuster and is best possible, since for n = 3 mod 18 there is a tournament with no perfect triangle packing and with all indegrees and outdegrees (n-1)/2 or (n-1)/2 \pm 1. Under the same hypotheses, we also show that one can embed any prescribed almost 1-factor, i.e. for any sequence n_1,...,n_t with n_1+...+n_t < n-O(1) we can find a vertex-disjoint collection of directed cycles with lengths n_1,...,n_t. In addition, under quite general conditions on the n_i we can remove the O(1) additive error and find a prescribed 1-factor. | |
| dc.description | 22 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/0806.2027 | |
| dc.identifier | http://arxiv.org/abs/0806.2027 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/162772 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C20, 05C70 | |
| dc.title | Triangle packings and 1-factors in oriented graphs | |
| dc.type | text |