{
  "id": "1009.4471",
  "version": "v1",
  "published": "2010-09-22T20:24:06.000Z",
  "updated": "2010-09-22T20:24:06.000Z",
  "title": "Boxicity of Line Graphs",
  "authors": [
    "L. Sunil Chandran",
    "Rogers Mathew",
    "Naveen Sivadasan"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Boxicity of a graph H, denoted by box(H), is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper, we show that for a line graph G of a multigraph, box(G) <= 2\\Delta(\\lceil log_2(log_2(\\Delta)) \\rceil + 3) + 1, where \\Delta denotes the maximum degree of G. Since \\Delta <= 2(\\chi - 1), for any line graph G with chromatic number \\chi, box(G) = O(\\chi log_2(log_2(\\chi))). For the d-dimensional hypercube H_d, we prove that box(H_d) >= (\\lceil log_2(log_2(d)) \\rceil + 1)/2. The question of finding a non-trivial lower bound for box(H_d) was left open by Chandran and Sivadasan in [L. Sunil Chandran and Naveen Sivadasan. The cubicity of Hypercube Graphs. Discrete Mathematics, 308(23):5795-5800, 2008]. The above results are consequences of bounds that we obtain for the boxicity of fully subdivided graphs (a graph which can be obtained by subdividing every edge of a graph exactly once).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-09-22T20:24:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "line graph",
      "non-trivial lower bound",
      "axis-parallel k-dimensional boxes",
      "intersection graph",
      "minimum integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1009.4471C"
    }
  }
}