{
  "id": "2308.05817",
  "version": "v1",
  "published": "2023-08-10T18:34:18.000Z",
  "updated": "2023-08-10T18:34:18.000Z",
  "title": "Comparing Width Parameters on Graph Classes",
  "authors": [
    "Nick Brettell",
    "Andrea Munaro",
    "Daniël Paulusma",
    "Shizhou Yang"
  ],
  "comment": "31 pages, 4 figures, abstract shortened due to arXiv requirements",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We study how the relationship between non-equivalent width parameters changes once we restrict to some special graph class. As width parameters, we consider treewidth, clique-width, twin-width, mim-width, sim-width and tree-independence number, whereas as graph classes we consider $K_{t,t}$-subgraph-free graphs, line graphs and their common superclass, for $t \\geq 3$, of $K_{t,t}$-free graphs. We first provide a complete comparison when restricted to $K_{t,t}$-subgraph-free graphs, showing in particular that treewidth, clique-width, mim-width, sim-width and tree-independence number are all equivalent. This extends a result of Gurski and Wanke (2000) stating that treewidth and clique-width are equivalent for the class of $K_{t,t}$-subgraph-free graphs. Next, we provide a complete comparison when restricted to line graphs, showing in particular that, on any class of line graphs, clique-width, mim-width, sim-width and tree-independence number are all equivalent, and bounded if and only if the class of root graphs has bounded treewidth. This extends a resut of Gurski and Wanke (2007) stating that a class of graphs~${\\cal G}$ has bounded treewidth if and only if the class of line graphs of graphs in ${\\cal G}$ has bounded clique-width. We then provide an almost-complete comparison for $K_{t,t}$-free graphs, leaving one missing case. Our main result is that $K_{t,t}$-free graphs of bounded mim-width have bounded tree-independence number. This result has structural and algorithmic consequences. In particular, it proves a special case of a conjecture of Dallard, Milani\\v{c} and \\v{S}torgel. Finally, we consider the question of whether boundedness of a certain width parameter is preserved under graph powers. We show that the question has a positive answer for sim-width precisely in the case of odd powers.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-10T18:34:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "line graphs",
      "tree-independence number",
      "subgraph-free graphs",
      "clique-width",
      "complete comparison"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}