Abstract
We say that a (di)graph G has a perfect H-packing if there exists a set of vertex-disjoint copies of H which cover all the vertices in G. The seminal Hajnal-Szemerédi theorem characterises the minimum degree that ensures a graph G contains a perfect K_r-packing. In this paper we prove the following analogue for directed graphs: Suppose that T is a tournament on r vertices and G is a digraph of sufficiently large order n where r divides n. If G has minimum in- and outdegree at least (1-1/r)n then G contains a perfect T-packing.
In the case when T is a cyclic triangle, this result verifies a recent conjecture of Czygrinow, Kierstead and Molla (for large digraphs).Furthermore, in the case when T is transitive we conjecture that it suffices for every vertex in G to have sufficiently large indegree or outdegree. We prove this conjecture for transitive triangles and asymptotically for all r ≥3. Our approach makes use of a result of Keevash and Mycroft concerning almost perfect matchings in hypergraphs as well as the Directed Graph Removal lemma.
In the case when T is a cyclic triangle, this result verifies a recent conjecture of Czygrinow, Kierstead and Molla (for large digraphs).Furthermore, in the case when T is transitive we conjecture that it suffices for every vertex in G to have sufficiently large indegree or outdegree. We prove this conjecture for transitive triangles and asymptotically for all r ≥3. Our approach makes use of a result of Keevash and Mycroft concerning almost perfect matchings in hypergraphs as well as the Directed Graph Removal lemma.
Original language | English |
---|---|
Pages (from-to) | 873-928 |
Number of pages | 56 |
Journal | Combinatorics, Probability and Computing |
Volume | 24 |
Issue number | 6 |
Early online date | 5 Feb 2015 |
DOIs | |
Publication status | Published - Nov 2015 |