9 papers
A polynomial bound on the pathwidth of graphs edge-coverable by 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 shortest paths has pathwidth at most . In this paper, we improve…
Basis Number of Graphs Excluding Minors
Colin Geniet, Ugo Giocanti
The basis number of a graph is the minimum such that the cycle space of is generated by a family of cycles using each edge at most times. A classical result of Mac…
A coarse Gallai theorem
Marc Distel, Ugo Giocanti, JÄdrzej Hodor +2
We prove that there exist functions and such that for all positive integers and , for every graph and every subset of the vertices of , either contain…
Coarse cops and robber in graphs and groups
Louis Esperet, Harmender Gahlawat, Ugo Giocanti
(abstract shortened to meet arxiv's length requirements) We investigate two variants of the classical Cops and robber game in graphs, recently introduced by Lee, MartÃnez-Pedroza,…
A note on the structure of locally finite planar quasi-transitive graphs
Ugo Giocanti
In an early work from 1896, Maschke established the complete list of all finite planar Cayley graphs. This result initiated a long line of research over the next century, aiming at…
Largest planar graphs of diameter and fixed maximum degree -- connection with fractional matchings
Antoine Dailly, Sasha Darmon, Ugo Giocanti +2
The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree and diameter . In this paper, we focus on planar graphs of diamete…