A theta in a graph is an induced subgraph consisting of two nonadjacent vertices joined by three disjoint paths. A prism in a graph is an induced subgraph consisting of two disjoint triangles joined by three disjoint paths. This paper gives a polynomial-time algorithm to test whether a graph has an induced subgraph that is either a prism or a theta.
All Science Journal Classification (ASJC) codes
- Detection algorithm
- Induced subgraph