Toward Grünbaum's Conjecture
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916118423142400 |
|---|---|
| author | Ortlieb, Christian Schmidt, Jens M. |
| author_facet | Ortlieb, Christian Schmidt, Jens M. |
| contents | Given a spanning tree $T$ of a planar graph $G$, the co-tree of $T$ is the spanning tree of the dual graph $G^*$ with edge set $(E(G)-E(T))^*$. Grünbaum conjectured in 1970 that every planar 3-connected graph $G$ contains a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most 3.
While Grünbaum's conjecture remains open, Biedl proved that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most 5. By using new structural insights into Schnyder woods, we prove that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most 4. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05681 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Toward Grünbaum's Conjecture Ortlieb, Christian Schmidt, Jens M. Discrete Mathematics Combinatorics Given a spanning tree $T$ of a planar graph $G$, the co-tree of $T$ is the spanning tree of the dual graph $G^*$ with edge set $(E(G)-E(T))^*$. Grünbaum conjectured in 1970 that every planar 3-connected graph $G$ contains a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most 3. While Grünbaum's conjecture remains open, Biedl proved that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most 5. By using new structural insights into Schnyder woods, we prove that there is a spanning tree $T$ such that $T$ and its co-tree have maximum degree at most 4. |
| title | Toward Grünbaum's Conjecture |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2402.05681 |