4 citations · 8 across the 12 of their papers we have counts for
14 papers
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…
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…
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 diameter…
Period-rigidity of one-relator groups
Solène J. Esnay, Ugo Giocanti, Etienne Moutot
We follow in this paper a recent line of work, consisting in characterizing the periodically rigid finitely generated groups, i.e., the groups for which every subshift of finite ty…
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…
Periodic colorings and orientations in infinite graphs
Tara Abrishami, Louis Esperet, Ugo Giocanti +3
We study the existence of periodic colorings and orientations in locally finite graphs. A coloring or orientation of a graph is periodic if the resulting colored or oriented gr…
Coarse geometry of quasi-transitive graphs beyond planarity
Louis Esperet, Ugo Giocanti
We study geometric and topological properties of infinite graphs that are quasi-isometric to a planar graph of bounded degree. We prove that every locally finite quasi-transitive g…
Optimization in graphical small cancellation theory
Louis Esperet, Ugo Giocanti
Gromov (2003) constructed finitely generated groups whose Cayley graphs contain all graphs from a given infinite sequence of expander graphs of unbounded girth and bounded diameter…
The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem
Louis Esperet, Ugo Giocanti, Clément Legrand-Duchesne
An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. In this paper we obtain a structure theorem for locally…
Twin-width V: linear minors, modular counting, and matrix multiplication
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +1
We continue developing the theory around the twin-width of totally ordered binary structures, initiated in the previous paper of the series. We first introduce the notion of parity…
Graphs with convex balls
Jérémie Chalopin, Victor Chepoi, Ugo Giocanti
In this paper, we investigate the graphs in which all balls are convex and the groups acting on them geometrically (which we call CB-graphs and CB-groups). These graphs have been i…
Twin-width IV: ordered graphs and matrices
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez +3
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a…