1 citations · 1 across the 3 of their papers we have counts for
6 papers
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…