{
  "id": "0807.4907",
  "version": "v2",
  "published": "2008-07-30T18:21:09.000Z",
  "updated": "2009-06-02T14:21:07.000Z",
  "title": "An Ore-type theorem for perfect packings in graphs",
  "authors": [
    "Daniela Kühn",
    "Deryk Osthus",
    "Andrew Treglown"
  ],
  "comment": "23 pages, 1 figure. Extra examples and a sketch proof of Theorem 4 added. To appear in the SIAM Journal on Discrete Mathematics",
  "categories": [
    "math.CO"
  ],
  "abstract": "We say that a graph G has a perfect H-packing (also called an H-factor) if there exists a set of disjoint copies of H in G which together cover all the vertices of G. Given a graph H, we determine, asymptotically, the Ore-type degree condition which ensures that a graph G has a perfect H-packing. More precisely, let \\delta_{\\rm Ore} (H,n) be the smallest number k such that every graph G whose order n is divisible by |H| and with d(x)+d(y)\\geq k for all non-adjacent x \\not = y \\in V(G) contains a perfect H-packing. We determine \\lim_{n\\to \\infty} \\delta_{\\rm Ore} (H,n)/n.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2009-06-02T14:21:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C35",
      "05C70"
    ],
    "keywords": [
      "perfect packings",
      "ore-type theorem",
      "perfect h-packing",
      "ore-type degree condition",
      "smallest number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0807.4907K"
    }
  }
}