-
Jozef Skokan, Separating the edges of a graph by a linear number of paths
Jozef Skokan, Separating the edges of a graph by a linear number of paths
Recently, Letzter proved that any graph of order n contains a collection P of $O(n \log^*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 Katona and confirming …