Botler–Naia conjecture on linear-size subdivision separating systems
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.