Botler–Naia conjecture on linear-size subdivision separating systems
Botler–Naia conjecture on linear-size subdivision separating systems
Let be a graph with at least one edge. A subdivision of is obtained by replacing edges of with pairwise internally vertex-disjoint paths; let be the class consisting of and all subdivisions of . A separating -system is a family of subgraphs from this class that separates the edges of the host graph. Botler–Naia conjecture. For every graph with at least one edge, there is a constant such that every -vertex graph admits a separating -system of size at most . Botler and Naia proved the corresponding assertion for and , with bounds and , respectively; the conjecture asks for the result for every graph 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.