{
  "id": "1001.0461",
  "version": "v1",
  "published": "2010-01-04T08:59:46.000Z",
  "updated": "2010-01-04T08:59:46.000Z",
  "title": "Rank-width of Random Graphs",
  "authors": [
    "Choongbum Lee",
    "Joonkyung Lee",
    "Sang-il Oum"
  ],
  "comment": "10 pages",
  "journal": "J. Graph Theory 70(July 2012)(3), pp. 339-347",
  "doi": "10.1002/jgt.20620",
  "categories": [
    "math.CO"
  ],
  "abstract": "Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour (2006). We investigate the asymptotic behavior of rank-width of a random graph G(n,p). We show that, asymptotically almost surely, (i) if 0<p<1 is a constant, then rw(G(n,p)) = \\lceil n/3 \\rceil-O(1), (ii) if 1/n<< p <1/2, then rw(G(n,p))= \\lceil n/3\\rceil-o(n), (iii) if p = c/n and c > 1, then rw(G(n,p)) > r n for some r = r(c), and (iv) if p <= c/n and c<1, then rw(G(n,p)) <=2. As a corollary, we deduce that G(n,p) has linear tree-width whenever p=c/n for each c>1, answering a question of Gao (2006).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-01-04T08:59:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C78"
    ],
    "keywords": [
      "random graph",
      "rank-width",
      "width parameter"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1001.0461L"
    }
  }
}