A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths

Julien Baste, Lucas De Meyer, Ugo Giocanti +2

Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by $k$ shortest paths has pathwidth at most $O(3^k)$. In this paper, we improve…