| Title: | Treewidth is NP-complete on cubic graphs |
|---|
| Authors: | ID Bodlaender, Hans L. (Author)
ID Bonnet, Édouard (Author)
ID Jaffke, Lars (Author)
ID Knop, Dušan (Author)
ID Lima, Paloma T. (Author)
ID Milanič, Martin (Author)
ID Ordyniak, Sebastian (Author)
ID Pandey, Sukanya (Author)
ID Suchý, Ondřej (Author) |
|---|
| Files: |  RAZ_Bodlaender_Hans_L._2025.pdf (550,69 KB)
MD5: A0B3102D0BCB3B966DE4D86EAB742B51
 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i3p36
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | IAM - Andrej Marušič Institute
|
|---|
| 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 |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 22.08.2025 |
|---|
| Year of publishing: | 2025 |
|---|
| Number of pages: | str. 1-23 |
|---|
| Numbering: | Vol. 32, iss. 3, article no. P3.36 |
|---|
| PID: | 20.500.12556/RUP-22238  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1077-8926 |
|---|
| DOI: | 10.37236/13205 |
|---|
| COBISS.SI-ID: | 261951235 |
|---|
| Publication date in RUP: | 18.12.2025 |
|---|
| Views: | 127 |
|---|
| Downloads: | 0 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
