{
  "id": "0906.1165",
  "version": "v1",
  "published": "2009-06-05T16:49:15.000Z",
  "updated": "2009-06-05T16:49:15.000Z",
  "title": "A Note on Threshold Dimension of Permutation Graphs",
  "authors": [
    "Diptendu Bhowmick"
  ],
  "comment": "8 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph $G(V,E)$ is a threshold graph if there exist non-negative reals $w_v, v \\in V$ and $t$ such that for every $U \\subseteq V$, $\\sum_{v \\in U} w_v\\leq t$ if and only if $U$ is a stable set. The {\\it threshold dimension} of a graph $G(V,E)$, denoted as $t(G)$, is the smallest integer $k$ such that $E$ can be covered by $k$ threshold spanning subgraphs of $G$. A permutation graph is a graph that can be represented as the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane. In this paper we will show that if $G$ is a permutation graph then $t(G) \\leq \\alpha(G)$ (where $\\alpha(G)$ is the cardinality of maximum independent set in $G$) and this bound is tight. As a corollary we will show that $t(G) \\leq \\frac{n}{2}$ where $n$ is the number of vertices in the permutation graph $G$. This bound is also tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-06-05T16:49:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "permutation graph",
      "threshold dimension",
      "maximum independent set",
      "smallest integer",
      "threshold spanning subgraphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0906.1165B"
    }
  }
}