Mader’s connectivity-keeping tree conjecture and the Luo–Tian–Wu bipartite conjecture
For every positive integer and every tree with bipartition , every -connected bipartite graph satisfying contains a subgraph such that is -connected.
References
- Connectivity keeping pendant extensions of paths in k-connected triangle-free graphs — arXiv — Menghan Ma, Qinghai Liu, Liping Zhang, Yanmei Hong
Source: arXiv
Progress summary
Recent papers settle important path-shaped and triangle-free cases, but neither the full tree conjecture nor its bipartite analogue is solved.
Mader’s conjecture, posed in 2012, predicts that sufficiently large minimum degree lets one delete any prescribed tree while preserving -connectivity. Luo, Tian, and Wu proposed the bipartite analogue in 2022, with a sharper bound determined by the tree’s bipartition.
Known results
- Mader proved the connectivity-preserving statement for paths; the general tree case was known for but remained open for .
- For bipartite graphs, the Luo–Tian–Wu bound is proved for odd-order paths; even-order paths are known with a bound larger by (March 7, 2025 publication).
- Earlier work handled several special tree families, including caterpillars and spiders for small .
October 2026 triangle-free and pendant-path advances
Menghan Ma, Qinghai Liu, Liping Zhang, and Yanmei Hong report optimal or sharpened minimum-degree bounds for paths and all pendant extensions of paths in -connected triangle-free graphs, including the conjectured bipartite cases. Related work proves Mader’s conjectured bound for pendant extensions of paths, while Chu, Fujita, Park, and Ryu obtain a broad triangle-free result for arbitrary trees. These are partial advances, not a solution of either full conjecture.
Current status (as of October 2026): The path cases and several restricted tree families are settled, but Mader’s conjecture for arbitrary trees and the full Luo–Tian–Wu bipartite conjecture remain open.
Solutions 0
No solutions have been posted yet.