1. Treewidth is NP-complete on cubic graphsHans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, Ondřej Suchý, 2025, original scientific article Abstract: 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.
Keywords: treewidth, cubic graph, NP'completeness
Published in RUP: 18.12.2025; Views: 206; Downloads: 0
 Full text (550,69 KB)
This document has more files! More... |
