Luo–Tian–Wu's bipartite connectivity-keeping tree conjecture

About 3 years old · traced to

Throughout, graphs are finite, simple, and undirected. Let \k\k be a positive integer, and let \T\T be a tree with bipartition (X,Y)(X,Y). A graph is \k\k-connected when its connectivity satisfies κ(G)≥k\kappa(G)\geq k; δ(G)\delta(G) denotes minimum degree, and \G−V(T′)\G-V(T') is the graph obtained by deleting the vertices of \T′\T'.

Luo–Tian–Wu's conjecture. Every \k\k-connected bipartite graph \G\G with

δ(G)≥k+max⁡{∣X∣,∣Y∣}\delta(G)\geq k+\max\{|X|,|Y|\}

contains a subtree \T′≅T\T'\cong T such that

κ(G−V(T′))≥k.\kappa(G-V(T'))\geq k.

This is the bipartite analogue of Mader's connectivity-keeping tree conjecture. The conjecture remains open for \k≥4\k\geq 4; the corresponding path result is known under a related minimum-degree condition.

References

Primary source

Hojin Chu, Shinya Fujita, Boram Park and Homoon Ryu, “Connectivity keeping trees in triangle-free graphs”, arXiv:2511.06622 (2025).

Additional references

2 papers in this index state this conjecture (2023–2025). The statement above is taken from the most recent of them; the others are arXiv:2303.03896.

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.