1 citations · 1 across the 6 of their papers we have counts for
8 papers
The coarse Erdős-Pósa theorem
Sandra Albrechtsen, Marthe Bonamy, Romain Bourneuf +1
We prove the coarse Erdős-Pósa conjecture of Georgakopoulos and Papasoglu. Informally, any graph either contains many fat cycles that are pairwise far apart, or there is a small nu…
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…
Bipartite Turán number of paths and other trees
Marthe Bonamy, Théotime Leclere, Timothé Picavet
We solve a recent question of Caro, Patkós and Tuza by determining the exact maximum number of edges in a bipartite connected graph as a function of the longest path it contains as…
On cuts of small chromatic number in sparse graphs
Guillaume Aubian, Marthe Bonamy, Romain Bourneuf +2
For a given integer , let denote the supremum such that every sufficiently large graph with average degree less than admits a separator $X \subseteq…
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…
On Modular Edge Colourings of Graphs
Gaétan Berthe, Marthe Bonamy, Fábio Botler +5
Given a graph and an integer , let denote the minimum number of colours required to colour the edges of such that, in each colour class, the subgraph ind…
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…
-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs
Marthe Bonamy, Colin Geniet
Merge-width, recently introduced by Dreier and Toruńczyk, is a common generalisation of bounded expansion classes and twin-width for which the first-order model checking problem re…