pith. sign in

arxiv: 1312.4101 · v1 · pith:6YNVDXX2new · submitted 2013-12-15 · 💻 cs.DM · math.CO

Trees and co-trees with constant maximum degree in planar 3-connected graphs

Therese Biedl This is my paper
classification 💻 cs.DM math.CO
keywords co-treeconnecteddegreemaximumplanarspanningtreeconjecture
0
0 comments X
read the original abstract

This paper considers the conjecture by Gr\"unbaum that every planar 3-connected graph has a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most 3. Here, the co-tree of $T$ is the spanning tree of the dual obtained by taking the duals of the non-tree edges. While Gr\"unbaum's conjecture remains open, we show that every planar 3-connected graph has a spanning tree $T$ such that both $T$ and its co-tree have maximum degree at most 5. It can be found in linear time.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. 3-packings in Triangulations: Algorithms, bounds, and Complexity

    cs.DM 2026-06 unverdicted novelty 6.0

    Proves λ_P3(G) ≥ ⌊n/5⌋ (asymptotically tight) and λ_{P2∪P1}(T) ≥ ⌊n/3⌋-2 (poly-time) in triangulations, with degree-based bounds and a face-path characterization for triangle factors.