| Naslov: | Treewidth is NP-complete on cubic graphs |
|---|
| Avtorji: | ID Bodlaender, Hans L. (Avtor)
ID Bonnet, Édouard (Avtor)
ID Jaffke, Lars (Avtor)
ID Knop, Dušan (Avtor)
ID Lima, Paloma T. (Avtor)
ID Milanič, Martin (Avtor)
ID Ordyniak, Sebastian (Avtor)
ID Pandey, Sukanya (Avtor)
ID Suchý, Ondřej (Avtor) |
|---|
| Datoteke: |  RAZ_Bodlaender_Hans_L._2025.pdf (550,69 KB)
MD5: A0B3102D0BCB3B966DE4D86EAB742B51
 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v32i3p36
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | IAM - Inštitut Andrej Marušič
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | treewidth, cubic graph, NP'completeness |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 22.08.2025 |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | str. 1-23 |
|---|
| Številčenje: | Vol. 32, iss. 3, article no. P3.36 |
|---|
| PID: | 20.500.12556/RUP-22238  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1077-8926 |
|---|
| DOI: | 10.37236/13205 |
|---|
| COBISS.SI-ID: | 261951235 |
|---|
| Datum objave v RUP: | 18.12.2025 |
|---|
| Število ogledov: | 118 |
|---|
| Število prenosov: | 0 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
