Quasi-tree-partitions of graphs with an excluded subgraph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914196040450048 |
|---|---|
| author | Liu, Chun-Hung Wood, David R. |
| author_facet | Liu, Chun-Hung Wood, David R. |
| contents | This paper studies the structure of graphs with given tree-width and excluding a fixed complete bipartite subgraph, which generalises the bounded degree setting. We give a new structural description of such graphs in terms of so-called quasi-tree-partitions. We demonstrate the utility of this result through applications to (fractional) clustered colouring. Further generalisations of these structural and colouring results are presented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00983 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quasi-tree-partitions of graphs with an excluded subgraph Liu, Chun-Hung Wood, David R. Combinatorics This paper studies the structure of graphs with given tree-width and excluding a fixed complete bipartite subgraph, which generalises the bounded degree setting. We give a new structural description of such graphs in terms of so-called quasi-tree-partitions. We demonstrate the utility of this result through applications to (fractional) clustered colouring. Further generalisations of these structural and colouring results are presented. |
| title | Quasi-tree-partitions of graphs with an excluded subgraph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.00983 |