Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 1164-1186 |
Number of pages | 23 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 22 |
Issue number | 3 |
DOIs | |
State | Published - 2008 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Mathematics
Keywords
- Detection algorithm
- Induced subgraph
- Prism
- Theta