20.500.12556/RUP-22238 Treewidth is NP-complete on cubic graphs The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2019 as a common generalization of avoidable vertices and simplicial paths. In 2020, Bonamy, Defrain, Hatzel, and Thiebaut proved that every graph containing an induced path of order k also contains an avoidable induced path of the same order. They also asked whether one could generalize this result to other avoidable structures, leaving the notion of avoidability up to interpretation. In this paper, we address this question: we specify the concept of avoidability for arbitrary graphs equipped with two terminal vertices. We provide both positive and negative results, some of which are related to a recent work by Chudnovsky, Norin, Seymour, and Turcotte in 2024. We also discuss several open questions. treewidth cubic graph NP'completeness drevesna širina kubičen graf NP-polnost true false true Angleški jezik Slovenski jezik Članek v reviji 2025-12-18 03:29:25 2025-12-18 03:29:29 2025-12-22 03:06:17 0000-00-00 00:00:00 2025 0 0 str. 1-23 iss. 3, article no. P3.36 Vol. 32 2025 0000-00-00 Zaloznikova NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2025-08-22 519.17 1077-8926 10.37236/13205 261951235 RAZ_Bodlaender_Hans_L._2025.pdf RAZ_Bodlaender_Hans_L._2025.pdf 1 A0B3102D0BCB3B966DE4D86EAB742B51 5e67dc4f29c9866d5a2ddbc83bfef37ef0efd6b76fa6c8386d5630d7e85f1088 dcc0a3fa-dbb9-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32293 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i3p36 1 b2caa758-dbb9-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32292 Inštitut Andrej Marušič 0 0 0