Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2505.19926 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916759624220672 |
|---|---|
| author | Dabrowski, Konrad K. Eagling-Vose, Tala Köhler, Noleen Ordyniak, Sebastian Paulusma, Daniël |
| author_facet | Dabrowski, Konrad K. Eagling-Vose, Tala Köhler, Noleen Ordyniak, Sebastian Paulusma, Daniël |
| contents | We determine if the width of a graph class ${\cal G}$ changes from unbounded to bounded if we consider only those graphs from ${\cal G}$ whose diameter is bounded. As parameters we consider treedepth, pathwidth, treewidth and clique-width, and as graph classes we consider classes defined by forbidding some specific graph $F$ as a minor, induced subgraph or subgraph, respectively. Our main focus is on treedepth for $F$-subgraph-free graphs of diameter at most~$d$ for some fixed integer $d$. We give classifications of boundedness of treedepth for $d\in \{4,5,\ldots\}$ and partial classifications for $d=2$ and $d=3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19926 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounding Width on Graph Classes of Constant Diameter Dabrowski, Konrad K. Eagling-Vose, Tala Köhler, Noleen Ordyniak, Sebastian Paulusma, Daniël Discrete Mathematics Data Structures and Algorithms Combinatorics We determine if the width of a graph class ${\cal G}$ changes from unbounded to bounded if we consider only those graphs from ${\cal G}$ whose diameter is bounded. As parameters we consider treedepth, pathwidth, treewidth and clique-width, and as graph classes we consider classes defined by forbidding some specific graph $F$ as a minor, induced subgraph or subgraph, respectively. Our main focus is on treedepth for $F$-subgraph-free graphs of diameter at most~$d$ for some fixed integer $d$. We give classifications of boundedness of treedepth for $d\in \{4,5,\ldots\}$ and partial classifications for $d=2$ and $d=3$. |
| title | Bounding Width on Graph Classes of Constant Diameter |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2505.19926 |