Linear-size separating path systems conjecture

Let GG be a graph on nn vertices. A separating path system is a collection of paths in GG that separates the edges of GG, either weakly or strongly. Linear-size separating path systems conjecture. There exists a constant cc such that every graph on nn vertices has a weakly- or strongly-separating path system of size at most cncn. This conjecture concerns Katona's question about the maximum minimum size of separating path systems over nn-vertex graphs. The source gives no resolution, so the conjecture remains open; the strongly separating version is slightly stronger than the weak version.

Sources & referencesView supporting material

Primary source

Shoham Letzter, “Separating paths systems of almost linear size”, arXiv:2211.07732 (2024).

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.