Linear-size separating path systems conjecture
Linear-size separating path systems conjecture
Let be a graph on vertices. A separating path system is a collection of paths in that separates the edges of , either weakly or strongly. Linear-size separating path systems conjecture. There exists a constant such that every graph on vertices has a weakly- or strongly-separating path system of size at most . This conjecture concerns Katona's question about the maximum minimum size of separating path systems over -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
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.