The (theta, wheel)-free graphs Part IV: induced paths and cycles
arXiv:1912.00516 · doi:10.1016/j.jctb.2020.06.002
Abstract
A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three internally vertex-disjoint paths of length at least 2 between the same pair of distinct vertices. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins. In this paper we use this decomposition theorem to solve several problems related to finding induced paths and cycles in our class.
References in corpus (9)
- Detecting induced subgraphs
- The k-in-a-path problem for claw-free graphs
- Combinatorial optimization with 2-joins
- Detecting 2-joins faster
- The -in-a-tree problem for graphs of girth at least~
- The four-in-a-tree problem in triangle-free graphs
- The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
- The (theta, wheel)-free graphs Part III: cliques, stable sets and coloring
- The (theta, wheel)-free graphs Part II: structure theorem