Avoidable Paths in Graphs
| Autor: | Meike Hatzel, Oscar Defrain, Marthe Bonamy, Jocelyn Thiebaut |
|---|---|
| Přispěvatelé: | Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Technical University of Berlin / Technische Universität Berlin (TU), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018), ANR-15-CE40-0009,GraphEn,Enumération dans les graphes et les hypergraphes: algorithmes et complexité(2015), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Technische Universität Berlin (TU), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM) |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Constructive Theoretical Computer Science Combinatorics Chordal graph Elementary proof [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Mathematics - Combinatorics Discrete Mathematics and Combinatorics Mathematics Mathematics::Combinatorics Conjecture Applied Mathematics Graph Computational Theory and Mathematics 010201 computation theory & mathematics 020201 artificial intelligence & image processing Combinatorics (math.CO) Geometry and Topology Computer Science - Discrete Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/9030 |
| Popis: | We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises the notion of simpliciality best known in the context of chordal graphs. The conjecture was only established for k in {1,2} (Ohtsuki et al. 1976, and Beisegel et al. 2019, respectively). Our result also implies a result of Chv\'atal et al. 2002, which assumed cycle restrictions. We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis. In the line of previous works, we discuss conditions for multiple avoidable paths to exist. Comment: 7 pages, 1 figure |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|