{
  "id": "math/0610262",
  "version": "v1",
  "published": "2006-10-08T17:32:18.000Z",
  "updated": "2006-10-08T17:32:18.000Z",
  "title": "Boxicity and Maximum degree",
  "authors": [
    "L. Sunil Chandran",
    "Mathew C. Francis",
    "Naveen Sivadasan"
  ],
  "comment": "4 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "An axis-parallel $d$--dimensional box is a Cartesian product $R_1 \\times R_2 \\times ... \\times R_d$ where $R_i$ (for $1 \\le i \\le d$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its \\emph{boxicity} $\\boxi(G)$ is the minimum dimension $d$, such that $G$ is representable as the intersection graph of (axis--parallel) boxes in $d$--dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research etc. We show that for any graph $G$ with maximum degree $\\Delta$, $\\boxi(G) \\le 2 \\Delta^2 + 2$. That the bound does not depend on the number of vertices is a bit surprising considering the fact that there are highly connected bounded degree graphs such as expander graphs. Our proof is very short and constructive. We conjecture that $\\boxi(G)$ is $O(\\Delta)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-10-08T17:32:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum degree",
      "boxicity finds applications",
      "operation research",
      "expander graphs",
      "minimum dimension"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math.....10262C"
    }
  }
}