Garamvölgyi–Jordán–Király–Villányi rigidity-packing conjectures

The conjectures, posed by Garamvölgyi, Jordán, Király and Villányi, ask for sharp connectivity conditions guaranteeing edge-disjoint rigid spanning subgraphs, including a rigid subgraph plus a spanning tree. The associated orientation bounds concern Thomassen’s conjecture.

Known results

• Villányi (2023): every $d(d+1)$-connected graph is rigid and globally rigid in $\mathbb{R}^d$; the coefficient is sharp.
• Villányi (2023): such graphs are $\binom{d+1}{2}+1$-redundantly rigid and $\binom{d+1}{2}$-redundantly globally rigid.
• Earlier work gave only $10td(d+1)$-connectivity for $t$ disjoint $d$-rigid spanning subgraphs and $320k^2$ for a $k$-connected orientation.

September 21, 2026 claimed settlement

The cited paper claims that every $K=\sum_i d_i(d_i+1)$-connected graph packs pairwise edge-disjoint spanning $d_i$-rigid subgraphs, sharply for $K\ge 4$, thereby settling both packing conjectures. It also claims $f(q)\le (25q^2+41q-16)/2$ and asymptotically $f(q)\le (8+o(1))q^2$; $f(q)=2q$ remains open. These claims are unverified.

Current status (as of September 2026): The two rigidity-packing conjectures are claimed settled sharply but remain unverified, while Thomassen’s orientation conjecture remains open.