{
  "id": "1603.00198",
  "version": "v1",
  "published": "2016-03-01T09:30:15.000Z",
  "updated": "2016-03-01T09:30:15.000Z",
  "title": "Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree",
  "authors": [
    "Martin Merker"
  ],
  "comment": "18 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The Tree Decomposition Conjecture by Bar\\'at and Thomassen states that for every tree $T$ there exists a natural number $k(T)$ such that the following holds: If $G$ is a $k(T)$-edge-connected simple graph with size divisible by the size of $T$, then $G$ can be edge-decomposed into subgraphs isomorphic to $T$. So far this conjecture has only been verified for paths, stars, and a family of bistars. We prove a weaker version of the Tree Decomposition Conjecture, where we require the subgraphs in the decomposition to be isomorphic to graphs that can be obtained from $T$ by vertex-identifications. We call such a subgraph a homomorphic copy of $T$. This implies the Tree Decomposition Conjecture under the additional constraint that the girth of $G$ is greater than the diameter of $T$. As an application, we verify the Tree Decomposition Conjecture for all trees of diameter at most 4.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-01T09:30:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C40",
      "05C51"
    ],
    "keywords": [
      "decomposing highly edge-connected graphs",
      "tree decomposition conjecture",
      "homomorphic copy",
      "fixed tree",
      "natural number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}