Separating the edges of a graph by a linear number of paths
Bonamy, M., Botler, F., Dross, F., Naia, T. & Skokan, J.
(2023).
Separating the edges of a graph by a linear number of paths.
Advances in Combinatorics,
https://doi.org/10.19086/aic.2023.6
(2023).
Separating the edges of a graph by a linear number of paths.
Advances in Combinatorics,
https://doi.org/10.19086/aic.2023.6
Recently, Letzter proved that any graph of order n contains a collection P of O(nlog⋆n) paths with the following property: for all distinct edges e and f there exists a path in P which contains e but not f . We improve this upper bound to 19n, thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. Our proof is elementary and self-contained.
