Grünbaum's conjecture on spanning trees and co-trees of planar graphs
Let be a planar 3-connected graph. A 3-tree is a spanning tree of with maximum degree at most . For a spanning tree of , let be the planar dual and define its co-tree by
Grünbaum's conjecture. Every planar 3-connected graph contains a 3-tree whose co-tree is also a 3-tree.
The conjecture strengthens the separate existence of bounded-degree spanning trees by requiring the spanning tree and its dual co-tree simultaneously to have maximum degree at most . It remains open; Biedl proved the weaker bound that there is a spanning tree such that both it and its co-tree have maximum degree at most .
References
Primary source
Christian Ortlieb and Jens M. Schmidt, “Toward Grünbaum's Conjecture”, arXiv:2402.05681 (2024).
Additional references
2 papers in this index state this conjecture (2013–2024). The statement above is taken from the most recent of them; the others are arXiv:1312.4101.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.