The minimum degree threshold for perfect graph packings
| dc.creator | Kühn, Daniela | |
| dc.creator | Osthus, Deryk | |
| dc.date | 2006-03-28 | |
| dc.date | 2008-02-01 | |
| dc.date.accessioned | 2026-07-07T08:57:34Z | |
| dc.date.available | 2026-07-07T08:57:34Z | |
| dc.description | Let H be any graph. We determine (up to an additive constant) the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let delta(H,n) denote the smallest integer t such that every graph G whose order n is divisible by |H| and with delta(G) > t contains a perfect H-packing. We show that delta(H,n) = (1-1/χ*(H))n+O(1). The value of chi*(H) depends on the relative sizes of the colour classes in the optimal colourings of H and satisfies k-1 < chi*(H) \le k, where k is the chromatic number of H. | |
| dc.description | revised and updated version, accepted for publication in Combinatorica | |
| dc.identifier | https://arxiv.org/abs/math/0603665 | |
| dc.identifier | http://arxiv.org/abs/math/0603665 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/147016 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C35, 05C70, 05C15 | |
| dc.title | The minimum degree threshold for perfect graph packings | |
| dc.type | text |