{
  "id": "1703.08675",
  "version": "v1",
  "published": "2017-03-25T11:07:25.000Z",
  "updated": "2017-03-25T11:07:25.000Z",
  "title": "The (theta, wheel)-free graphs Part II: structure theorem",
  "authors": [
    "Marko Radovanović",
    "Nicolas Trotignon",
    "Kristina Vušković"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this paper we obtain a decomposition theorem for the class of graphs that do not contain an induced subgraph isomorphic to a theta or a wheel, i.e. the class of (theta, wheel)-free graphs. The decomposition theorem uses clique cutsets and 2-joins. Clique cutsets are vertex cutsets that work really well in decomposition based algorithms, but are unfortunately not strong enough to decompose more complex hereditary graph classes. A 2-join is an edge cutset that appeared in decomposition theorems of several complex classes, such as perfect graphs, even-hole-free graphs and others. In these decomposition theorems 2-joins are used together with vertex cutsets that are stronger than clique cutsets, such as star cutsets and their generalizations (which are much harder to use in algorithms). This is a first example of a decomposition theorem that uses just the combination of clique cutsets and 2-joins. This has several consequences. First, we can easily transform our decomposition theorem into a complete structure theorem for (theta, wheel)-free graphs, i.e. we show how every (theta, wheel)-free graph can be built starting from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations; and all graphs built this way are (theta, wheel)-free. Such structure theorems are very rare for hereditary graph classes, only a few examples are known. Secondly, we obtain an $\\mathcal O (n^4m)$-time decomposition based recognition algorithm for (theta, wheel)-free graphs. Finally, in Part III of this series, we give further applications of our decomposition theorem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-03-25T11:07:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C75"
    ],
    "keywords": [
      "decomposition theorem",
      "graphs part",
      "clique cutsets",
      "complex hereditary graph classes",
      "vertex cutsets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}