Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2509.16786 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915504753475584 |
|---|---|
| author | Nguyen, Tung Scott, Alex Seymour, Paul |
| author_facet | Nguyen, Tung Scott, Alex Seymour, Paul |
| contents | For finite graphs, path-width is an interesting and useful concept, but if we extend it to infinite graphs in the most obvious way (by making the indexing path infinite), it does not work nicely. The simplest extension that works nicely is to allow the indexing set to be any totally-ordered set, and then the corresponding decomposition is called a ``line-decomposition'', and the maximum bag size needed is called ``line-width''.
In particular, the indexing set need not be a well-order; but the corresponding decomposition would be easier to use if it was. We show that if a graph has line-width at most $k$, it admits a well-ordered line-decomposition with width at most $2k$, and this is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16786 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Line-width and path-width Nguyen, Tung Scott, Alex Seymour, Paul Combinatorics 05C63, 06A05 For finite graphs, path-width is an interesting and useful concept, but if we extend it to infinite graphs in the most obvious way (by making the indexing path infinite), it does not work nicely. The simplest extension that works nicely is to allow the indexing set to be any totally-ordered set, and then the corresponding decomposition is called a ``line-decomposition'', and the maximum bag size needed is called ``line-width''. In particular, the indexing set need not be a well-order; but the corresponding decomposition would be easier to use if it was. We show that if a graph has line-width at most $k$, it admits a well-ordered line-decomposition with width at most $2k$, and this is best possible. |
| title | Line-width and path-width |
| topic | Combinatorics 05C63, 06A05 |
| url | https://arxiv.org/abs/2509.16786 |