{
  "id": "1811.08994",
  "version": "v1",
  "published": "2018-11-22T02:10:29.000Z",
  "updated": "2018-11-22T02:10:29.000Z",
  "title": "Separation Dimension and Degree",
  "authors": [
    "Alex Scott",
    "David R. Wood"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The \"separation dimension\" of a graph $G$ is the minimum positive integer $d$ for which there is an embedding of $G$ into $\\mathbb{R}^d$, such that every pair of disjoint edges are separated by some axis-parallel hyperplane. We prove a conjecture of Alon et al. [SIAM J. Discrete Math. 2015] by showing that every graph with maximum degree $\\Delta$ has separation dimension less than $20\\Delta$, which is best possible up to a constant factor. We also prove that graphs with separation dimension 3 have bounded average degree and bounded chromatic number, partially resolving an open problem by Alon et al. [J. Graph Theory 2018].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-11-22T02:10:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "separation dimension",
      "disjoint edges",
      "axis-parallel hyperplane",
      "discrete math",
      "graph theory"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}