Separating Path Systems of Size at most
In the authors' words
A family of paths in a graph strongly separates the edges of if for every ordered pair of distinct edges some path in the family contains and avoids ; the minimum size of such a family is denoted by . Bonamy, Botler, Dross, Naia, and Skokan proved, for every -vertex graph , that ; Liu, Xu, and Yang recently improved this to . We prove, for every -vertex graph , that .
Main resultThe abstract does not state a limitation.
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.