{
  "id": "2204.07670",
  "version": "v1",
  "published": "2022-04-15T22:44:23.000Z",
  "updated": "2022-04-15T22:44:23.000Z",
  "title": "Twin-width can be exponential in treewidth",
  "authors": [
    "Édouard Bonnet",
    "Hugues Déprés"
  ],
  "comment": "11 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "For any small positive real $\\varepsilon$ and integer $t > \\frac{1}{\\varepsilon}$, we build a graph with a vertex deletion set of size $t$ to a tree, and twin-width greater than $2^{(1-\\varepsilon) t}$. In particular, this shows that the twin-width is sometimes exponential in the treewidth, in the so-called oriented twin-width and grid number, and that adding an apex may multiply the twin-width by at least $2-\\varepsilon$. Except for the one in oriented twin-width, these lower bounds are essentially tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-04-15T22:44:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75",
      "05C05",
      "G.2.2"
    ],
    "keywords": [
      "exponential",
      "oriented twin-width",
      "vertex deletion set",
      "grid number",
      "twin-width greater"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}