## Abstract

We say that a 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´edi theorem [12] characterises the minimum degree that ensures a graph G contains a perfect Kr-packing. Balogh,

Kostochka and Treglown [4] proposed a degree sequence version of the Hajnal–Szemer´edi theorem which, if true, gives a strengthening of the Hajnal–Szemer´edi theorem. In this paper we prove this conjecture asymptotically. Another fundamental result in the area is the Alon–Yuster theorem [3] which gives a minimum degree condition that ensures a graph contains a perfect H-packing for an arbitrary graph H. We give a wide-reaching generalisation of this result by answering another conjecture of Balogh, Kostochka and Treglown [4] on the degree sequence of a graph that forces a perfect H-packing. We also prove a degree sequence result concerning perfect transitive tournament packings in directed graphs. The proofs blend together the regularity and absorbing methods.

copies of H which cover all the vertices in G. The seminal Hajnal–Szemer´edi theorem [12] characterises the minimum degree that ensures a graph G contains a perfect Kr-packing. Balogh,

Kostochka and Treglown [4] proposed a degree sequence version of the Hajnal–Szemer´edi theorem which, if true, gives a strengthening of the Hajnal–Szemer´edi theorem. In this paper we prove this conjecture asymptotically. Another fundamental result in the area is the Alon–Yuster theorem [3] which gives a minimum degree condition that ensures a graph contains a perfect H-packing for an arbitrary graph H. We give a wide-reaching generalisation of this result by answering another conjecture of Balogh, Kostochka and Treglown [4] on the degree sequence of a graph that forces a perfect H-packing. We also prove a degree sequence result concerning perfect transitive tournament packings in directed graphs. The proofs blend together the regularity and absorbing methods.

Original language | English |
---|---|

Pages (from-to) | 13-41 |

Number of pages | 31 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 118 |

Early online date | 28 Jan 2016 |

DOIs | |

Publication status | Published - May 2016 |

## Keywords

- Perfect packing
- Absorbing method
- Regularity method