{
  "id": "1410.5750",
  "version": "v1",
  "published": "2014-10-21T17:31:38.000Z",
  "updated": "2014-10-21T17:31:38.000Z",
  "title": "Edge-decompositions of graphs with high minimum degree",
  "authors": [
    "Ben Barber",
    "Daniela Kühn",
    "Allan Lo",
    "Deryk Osthus"
  ],
  "comment": "38 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here a graph $G$ is $F$-divisible if $e(F)$ divides $e(G)$ and the greatest common divisor of the degrees of $F$ divides the greatest common divisor of the degrees of $G$, and $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$. We extend this result to graphs which are allowed to be far from complete: our results imply that every sufficiently large $F$-divisible graph $G$ on $n$ vertices with minimum degree at least $(1- ( 9 |F|^{10})^{-1} +\\epsilon)n$ has an $F$-decomposition. Moreover, every sufficiently large $K_3$-divisible graph of minimum degree $0.956n$ has a $K_3$-decomposition. Our result significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large $K_3$-divisible graph with minimum degree $3n/4$ has a $K_3$-decomposition. For certain graphs, we can strengthen the general bound above. In particular, we obtain the asymptotically correct threshold of $n/2+o(n)$ for even cycles of length at least 6. Our main contribution is a general method which turns an approximate decomposition into an exact one.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-10-21T17:31:38.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70"
    ],
    "keywords": [
      "high minimum degree",
      "sufficiently large",
      "greatest common divisor",
      "divisible graph",
      "edge-decompositions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 38,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1410.5750B"
    }
  }
}