Grünbaum's conjecture on spanning trees and co-trees of planar graphs

About 13 years old · traced to

Let GG be a planar 3-connected graph. A 3-tree is a spanning tree of GG with maximum degree at most 33. For a spanning tree TT of GG, let G∗=(V∗,E∗)G^*=(V^*,E^*) be the planar dual and define its co-tree by

¬T∗:=(V∗,(E(G)−E(T))∗).\neg T^*:= (V^*,(E(G)-E(T))^*).

Grünbaum's conjecture. Every planar 3-connected graph GG contains a 3-tree TT whose co-tree ¬T∗\neg T^* 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 33. 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 55.

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

Never refreshed

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.