9 citations · 21 across the 18 of their papers we have counts for
22 papers
Meta-Theorems for Cuttable Distributed Problems
Marthe Bonamy, Avinandan Das, Cyril Gavoille +3
We prove that given any -approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an -round -approximation LOCAL algorithm…
Tree-independence number of -free graphs with no large bicliques
Václav Blažej, J. Pascal Gollin, Tomáš Hons +5
The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bo…
Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1
We give a new, short proof that graphs embeddable in a given Euler genus- surface admit a simple -round -approximation distributed algorithm for Minimum Dominating Set…
Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors
Marthe Bonamy, Cyril Gavoille, Timothé Picavet +1
We show that graphs excluding as a minor admit a -round -approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Min…
Faithful universal graphs for minor-closed classes
Paul Bastide, Louis Esperet, Carla Groenland +3
It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We pro…
Subgraph-universal planar graphs for trees
Helena Bergold, Vesna Iršič, Robert Lauff +3
We show that there exists an outerplanar graph on vertices for that contains every tree on vertices as a subgraph. This exten…
On the local resilience of random geometric graphs with respect to connectivity and long cycles
Alberto Espuny Díaz, Lyuben Lichev, Alexandra Wesolek
Given an increasing graph property , a graph is -resilient with respect to if, for every spanning subgraph where each vertex keeps…
Cops and Robber on Hyperbolic Manifolds
Vesna Iršič, Bojan Mohar, Alexandra Wesolek
The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pu…
A Note on the 2-Colored Rectilinear Crossing Number of Random Point Sets in the Unit Square
Sergio Cabello, Éva Czabarka, Ruy Fabila-Monroy +5
Let be a set of four points chosen independently, uniformly at random from a square. Join every pair of points of with a straight line segment. Color these edges red if the…
Reconfiguration of plane trees in convex geometric graphs
Nicolas Bousquet, Lucas De Meyer, Théo Pierron +1
A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip se…
On Minimizing the Energy of a Spherical Graph Representation
Matt DeVos, Danielle Rogers, Alexandra Wesolek
Graph representations are the generalization of geometric graph drawings from the plane to higher dimensions. A method introduced by Tutte to optimize properties of graph drawings…
Sharp threshold for embedding balanced spanning trees in random geometric graphs
Alberto Espuny Díaz, Lyuben Lichev, Dieter Mitsche +1
A rooted tree is balanced if the degree of a vertex depends only on its distance to the root. In this paper we determine the sharp threshold for the appearance of a large family of…
Maximum Independent Set when excluding an induced minor: and
Édouard Bonnet, Julien Duron, Colin Geniet +2
Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph as an induced minor, Maximum Independent Set can be solved in polynomial time, a…
A note on highly connected -minor free graphs
Nicolas Bousquet, Théo Pierron, Alexandra Wesolek
We show that every -connected -minor free graph with minimum degree at least has maximum degree at most . As a consequence, we show that every 3-connected…
Cops and Robber game in higher-dimensional manifolds with spherical and Euclidean metric
Vesna Iršič, Bojan Mohar, Alexandra Wesolek
The recently introduced variation of the game of cops and robber is played on geodesic spaces. In this paper we establish some general strategies for the players, in particular the…
Every graph is eventually Turán-good
Natasha Morrison, JD Nir, Sergey Norin +2
Let be a graph. We show that if is large enough as a function of , then the -partite Turán graph maximizes the number of copies of among all -free graphs…
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés +5
A graph is -free if it does not contain pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite g…
On Asymptotic Packing of Geometric Graphs
Daniel W. Cranston, Jiaxi Nie, Jacques Verstraëte +1
A set of geometric graphs is {\em geometric-packable} if it can be asymptotically packed into every sequence of drawings of the complete graph . For example, the set of geomet…
A tight local algorithm for the minimum dominating set problem in outerplanar graphs
Marthe Bonamy, Linda Cook, Carla Groenland +1
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We…
A note on connected greedy edge colouring
Marthe Bonamy, Carla Groenland, Carole Muller +3
Following a given ordering of the edges of a graph , the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus i…
Limiting crossing numbers for geodesic drawings on the sphere
Marthe Bonamy, Bojan Mohar, Alexandra Wesolek
We introduce a model for random geodesic drawings of the complete bipartite graph on the unit sphere in , where we select the vertices in eac…
Bootstrap percolation in Ore-type graphs
Alexandra Wesolek
The -neighbour bootstrap process describes an infection process on a graph, where we start with a set of initially infected vertices and an uninfected vertex becomes infected as…