Trees and co-trees in planar 3-connected graphs An easier proof via Schnyder woods
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_ | 1866916273618681856 |
|---|---|
| author | Ortlieb, Christian Schmidt, Jens M. |
| author_facet | Ortlieb, Christian Schmidt, Jens M. |
| contents | Let $G$ be a 3-connected planar graph. Define the co-tree of a spanning tree $T$ of $G$ as the graph induced by the dual edges of $E(G)-E(T)$. The well-known cut-cycle duality implies that the co-tree is itself a tree. Let a $k$-tree be a spanning tree with maximum degree $k$. In 1970, Grünbaum conjectured that every 3-connected planar graph contains a 3-tree whose co-tree is also a 3-tree. In 2014, Biedl showed that every such graph contains a 5-tree whose co-tree is a 5-tree. In this paper, we present an easier proof of Biedl's result |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01230 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Trees and co-trees in planar 3-connected graphs An easier proof via Schnyder woods Ortlieb, Christian Schmidt, Jens M. Discrete Mathematics Combinatorics Let $G$ be a 3-connected planar graph. Define the co-tree of a spanning tree $T$ of $G$ as the graph induced by the dual edges of $E(G)-E(T)$. The well-known cut-cycle duality implies that the co-tree is itself a tree. Let a $k$-tree be a spanning tree with maximum degree $k$. In 1970, Grünbaum conjectured that every 3-connected planar graph contains a 3-tree whose co-tree is also a 3-tree. In 2014, Biedl showed that every such graph contains a 5-tree whose co-tree is a 5-tree. In this paper, we present an easier proof of Biedl's result |
| title | Trees and co-trees in planar 3-connected graphs An easier proof via Schnyder woods |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2402.01230 |