2014/06/12 by Treglown, Andrew · 3 citations
#05C20 #05C35 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1406.3229
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 Kr-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.