The (theta, wheel)-free graphs Part IV: Induced paths and cycles
| Autor: | Nicolas Trotignon, Kristina Vušković, Marko Radovanović |
|---|---|
| Přispěvatelé: | Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
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 |
| Zdroj: | 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⟩ |
| ISSN: | 0095-8956 1096-0902 |
| DOI: | 10.1016/j.jctb.2020.06.002⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect