ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a graph on nn vertices. A path separating system of GG is a collection of paths in GG such that, for every ordered pair of distinct edges (e,f)(e,f), some path contains ee but not ff. Balogh et al.'s conjecture. Every graph of order nn admits a path separating system of size O⁡(n)\operatorname{O}(n). This strengthened conjecture was confirmed in 2023, when a separating path system of size at most 19n19n was proved for every graph on nn vertices.

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.