The half-degree matching-removability conjecture

Less than 1 year old · traced to

For k≥1k\ge 1, a vertex set SS in a kk-connected graph GG is kk-removable when G−SG-S remains kk-connected; a matching is kk-removable when its edge deletion leaves a kk-connected graph. The half-degree matching-removability conjecture. Every kk-connected graph GG with δ(G)≥k+1\delta(G)\ge k+1 contains a kk-removable ⌈(δ(G)+1)/2⌉\lceil(\delta(G)+1)/2\rceil-matching, unless δ(G)\delta(G) is even and G≅Kδ(G)+1G\cong K_{\delta(G)+1}. The paper's theorem supports this for k≤3k\le 3, except for the case k=3k=3 and δ(G)=4\delta(G)=4; the general conjecture remains open.

References

Primary source

Hengzhe Li, Mingming Zhou, Shinya Fujita and Yaping Mao, “From Halin's Edge Removability to Matching Removability in k-Connected Graphs”, arXiv:2605.24035 (2026).

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.