mercredi 7 janvier 2026

par BUTEL Nathalie

Ugo Giocanti, chercheur postdoctoral à Jagiellonian University in Kraków (Pologne), donnera un séminaire le mercredi 7 janvier 2026 à 14h au Centre Inria d'Université Côte d'Azur dans la salle Euler Violet.

TITLE : 

Structure of graphs coverable by a few isometric paths or trees 

ABSTRACT : 

Dumas, Foucaud, Perez and Todinca [SIAM J. Disc. Math., 2024] recently proved that every graph whose edge set can be covered by k shortest paths has pathwidth at most $3^k$. I will show that one can improve this upper bound on the pathwidth to a polynomial bound ; namely, every graph whose edge set can be covered by k shortest paths has pathwidth $O(k^4)$, answering a question from the same paper. I will also mention some related results and questions about the optimal bounds, and some coarse generalisations. 
Eventually, I will mention similar questions and partial results about the structure of graphs coverable by a few number of isometric subtrees (a subtree of a graph G is isometric if all its paths are shortest paths of G). 
Joint work with Julien Baste, Lucas De Meyer, Etienne Objois and Timothé Picavet.