Back to Search
Start Over
The (theta, wheel)-free graphs Part IV: Induced paths and cycles
- Source :
- Journal of Combinatorial Theory, Series B, Journal of Combinatorial Theory, Series B, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩, Journal of Combinatorial Theory, Series B, Elsevier, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩
- Publication Year :
- 2021
- Publisher :
- HAL CCSD, 2021.
-
Abstract
- International audience; 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.
- Subjects :
- 010102 general mathematics
Induced subgraph
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Graph
Theoretical Computer Science
Combinatorics
Computational Theory and Mathematics
010201 computation theory & mathematics
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Mathematics
Decomposition theorem
Subjects
Details
- Language :
- English
- ISSN :
- 00958956 and 10960902
- Database :
- OpenAIRE
- Journal :
- Journal of Combinatorial Theory, Series B, Journal of Combinatorial Theory, Series B, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩, Journal of Combinatorial Theory, Series B, Elsevier, 2021, 146, pp.495-531. ⟨10.1016/j.jctb.2020.06.002⟩
- Accession number :
- edsair.doi.dedup.....a760ef213c8975b2e181a64d618913db