{
  "id": "2105.02516",
  "version": "v1",
  "published": "2021-05-06T08:40:55.000Z",
  "updated": "2021-05-06T08:40:55.000Z",
  "title": "On the Boxicity of Kneser Graphs and Complements of Line Graphs",
  "authors": [
    "Marco Caoduro",
    "Lyuben Lichev"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "An axis-parallel $d$-dimensional box is a cartesian product $I_1\\times I_2\\times \\dots \\times I_b$ where $I_i$ is a closed sub-interval of the real line. For a graph $G = (V,E)$, the $boxicity \\ of \\ G$, denoted by $\\text{box}(G)$, is the minimum dimension $d$ such that $G$ is the intersection graph of a family $(B_v)_{v\\in V}$ of $d$-dimensional boxes in $\\mathbb R^d$. Let $k$ and $n$ be two positive integers such that $n\\geq 2k+1$. The $Kneser \\ graph$ $Kn(k,n)$ is the graph with vertex set given by all subsets of $\\{1,2,\\dots,n\\}$ of size $k$ where two vertices are adjacent if their corresponding $k$-sets are disjoint. In this note, we derive a general upper bound for $\\text{box}(Kn(k,n))$, and a lower bound in the case $n\\ge 2k^3-2k^2+1$, which matches the upper bound up to an additive factor of $\\Theta(k^2)$. Our second contribution is to provide upper and lower bounds for the boxicity of the complement of the line graph of any graph $G$, and as a corollary, we derive that $\\text{box}(Kn(2,n))\\in \\{n-3, n-2\\}$ for every $n\\ge 5$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-05-06T08:40:55.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C62"
    ],
    "keywords": [
      "line graph",
      "kneser graphs",
      "complement",
      "dimensional box",
      "lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}