Back to Search
Start Over
The (theta, wheel)-free graphs Part IV: Induced paths and cycles.
- Source :
-
Journal of Combinatorial Theory - Series B . Jan2021, Vol. 146, p495-531. 37p. - Publication Year :
- 2021
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *WHEELS
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 146
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 147116836
- Full Text :
- https://doi.org/10.1016/j.jctb.2020.06.002