Botler–Naia conjecture on linear-size subdivision separating systems

Let HH be a graph with at least one edge. A subdivision of HH is obtained by replacing edges of HH with pairwise internally vertex-disjoint paths; let Sub(H)\operatorname{Sub}(H) be the class consisting of K2K_2 and all subdivisions of HH. A separating Sub(H)\operatorname{Sub}(H)-system is a family of subgraphs from this class that separates the edges of the host graph. Botler–Naia conjecture. For every graph HH with at least one edge, there is a constant CH>0C_H>0 such that every nn-vertex graph admits a separating Sub(H)\operatorname{Sub}(H)-system of size at most CHnC_Hn. Botler and Naia proved the corresponding assertion for H=K3H=K_3 and H=K4H=K_4, with bounds 41n41n and 82n82n, respectively; the conjecture asks for the result for every graph HH with an edge.

Sources & referencesView supporting material

Primary source

George Kontogeorgiou, Matias Pavez-Signe, Maya Stein, S Taruni and Ana Trujillo-Negrete, “Separating edges by linearly many subdivisions”, arXiv:2506.14011 (2025).

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.