Separating the edges of a graph by a linear number of paths

Recently, Letzter proved that any graph of order \(n\) contains a collection \(\mathcal{P}\) of \(O(n\log^\star n)\) paths with the following property: for all distinct edges \(e\) and \(f\) there exists a path in \(\mathcal{P}\) which contains \(e\) but not \(f\). We improve this upper bound to \(1...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-10
Main Authors: Bonamy, Marthe, Botler, Fábio, Dross, François, Naia, Tássio, Skokan, Jozef
Format: Article
Language:English
Subjects:
Graph theory
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recently, Letzter proved that any graph of order \(n\) contains a collection \(\mathcal{P}\) of \(O(n\log^\star n)\) paths with the following property: for all distinct edges \(e\) and \(f\) there exists a path in \(\mathcal{P}\) which contains \(e\) but not \(f\). We improve this upper bound to \(19 n\), 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.
ISSN:2331-8422
DOI:10.48550/arxiv.2301.08707