ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.