Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2302.04783 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913402100645888 |
|---|---|
| author | Cocks, Daniel |
| author_facet | Cocks, Daniel |
| contents | It has long been known that the following basic objects are obstructions to bounded tree-width: for arbitrarily large $t$, $(1)$ the complete graph $K_t$, $(2)$ the complete bipartite graph $K_{t,t}$, $(3)$ a subdivision of the $(t \times t)$-wall and $(4)$ the line graph of a subdivision of the $(t \times t)$-wall. We now add a further \emph{boundary object} to this list, a \emph{$t$-sail}.
These results have been obtained by studying sparse hereditary \emph{path-star} graph classes, each of which consists of the finite induced subgraphs of a single infinite graph whose edges can be partitioned into a path (or forest of paths) with a forest of stars, characterised by an infinite word over a possibly infinite alphabet. We show that a path-star class whose infinite graph has an unbounded number of stars, each of which connects an unbounded number of times to the path, has unbounded tree-width. In addition, we show that such a class is not a subclass of the hereditary class of circle graphs.
We identify a collection of \emph{nested} words with a recursive structure that exhibit interesting characteristics when used to define a path-star graph class. These graph classes do not contain any of the four basic obstructions but instead contain graphs that have large tree-width if and only if they contain arbitrarily large $t$-sails. We show that these classes are infinitely defined and, like classes of bounded degree or classes excluding a fixed minor, do not contain a minimal class of unbounded tree-width. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_04783 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | $t$-sails and sparse hereditary classes of unbounded tree-width Cocks, Daniel Combinatorics Data Structures and Algorithms 05C75, 05C85 It has long been known that the following basic objects are obstructions to bounded tree-width: for arbitrarily large $t$, $(1)$ the complete graph $K_t$, $(2)$ the complete bipartite graph $K_{t,t}$, $(3)$ a subdivision of the $(t \times t)$-wall and $(4)$ the line graph of a subdivision of the $(t \times t)$-wall. We now add a further \emph{boundary object} to this list, a \emph{$t$-sail}. These results have been obtained by studying sparse hereditary \emph{path-star} graph classes, each of which consists of the finite induced subgraphs of a single infinite graph whose edges can be partitioned into a path (or forest of paths) with a forest of stars, characterised by an infinite word over a possibly infinite alphabet. We show that a path-star class whose infinite graph has an unbounded number of stars, each of which connects an unbounded number of times to the path, has unbounded tree-width. In addition, we show that such a class is not a subclass of the hereditary class of circle graphs. We identify a collection of \emph{nested} words with a recursive structure that exhibit interesting characteristics when used to define a path-star graph class. These graph classes do not contain any of the four basic obstructions but instead contain graphs that have large tree-width if and only if they contain arbitrarily large $t$-sails. We show that these classes are infinitely defined and, like classes of bounded degree or classes excluding a fixed minor, do not contain a minimal class of unbounded tree-width. |
| title | $t$-sails and sparse hereditary classes of unbounded tree-width |
| topic | Combinatorics Data Structures and Algorithms 05C75, 05C85 |
| url | https://arxiv.org/abs/2302.04783 |