b'Marthe Bonamy'

research

∙ 02/26/2023

Partitioning edges of a planar graph into linear forests and a matching

We show that the edges of any planar graph of maximum degree at most 9 c...

0 Marthe Bonamy, et al. ∙

research

∙ 01/20/2023

Separating the edges of a graph by a linear number of paths

Recently, Letzter proved that any graph of order n contains a collection...

0 Marthe Bonamy, et al. ∙

research

∙ 06/01/2022

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth

A graph is O_k-free if it does not contain k pairwise vertex-disjoint an...

0 Marthe Bonamy, et al. ∙

research

∙ 12/04/2021

Kempe changes in degenerate graphs

We consider Kempe changes on the k-colorings of a graph on n vertices. I...

0 Marthe Bonamy, et al. ∙

research

∙ 10/28/2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

A (unit) disk graph is the intersection graph of closed (unit) disks in ...

0 Marthe Bonamy, et al. ∙

research

∙ 10/20/2021

Improved pyrotechnics : Closer to the burning graph conjecture

Can every connected graph burn in ⌈√(n)⌉ steps? While this conjecture re...

0 Paul Bastide, et al. ∙

research

∙ 08/05/2021

A tight local algorithm for the minimum dominating set problem in outerplanar graphs

We show that there is a deterministic local algorithm (constant-time dis...

0 Marthe Bonamy, et al. ∙

research

∙ 07/16/2021

On Vizing's edge colouring question

Soon after his 1964 seminal paper on edge colouring, Vizing asked the fo...

0 Marthe Bonamy, et al. ∙

research

∙ 05/20/2021

Tuza's Conjecture for Threshold Graphs

Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjo...

0 Marthe Bonamy, et al. ∙

research

∙ 03/19/2021

On a recolouring version of Hadwiger's conjecture

We prove that for any ε>0, for any large enough t, there is a graph G th...

0 Marthe Bonamy, et al. ∙

research

∙ 12/04/2020

Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces

The asymptotic dimension is an invariant of metric spaces introduced by ...

0 Marthe Bonamy, et al. ∙

research

∙ 12/03/2020

Optimal labelling schemes for adjacency, comparability and reachability

We construct asymptotically optimal adjacency labelling schemes for ever...

0 Marthe Bonamy, et al. ∙

research

∙ 08/24/2020

Limiting crossing numbers for geodesic drawings on the sphere

We introduce a model for random geodesic drawings of the complete bipart...

0 Marthe Bonamy, et al. ∙

research

∙ 08/08/2020

A note on deterministic zombies

"Zombies and Survivor" is a variant of the well-studied game of "Cops an...

0 Valentin Bartier, et al. ∙

research

∙ 04/15/2020

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets

Enumerating minimal transversals in a hypergraph is a notoriously hard p...

0 Marthe Bonamy, et al. ∙

research

∙ 02/10/2020

On the effect of symmetry requirement for rendezvous on the complete graph

We consider a classic rendezvous game where two players try to meet each...

0 Marthe Bonamy, et al. ∙

research

∙ 12/06/2019

Dominating sets reconfiguration under token sliding

Let G be a graph and D_s and D_t be two dominating sets of G of size k. ...

0 Marthe Bonamy, et al. ∙

research

∙ 12/03/2019

Jones' Conjecture in subcubic graphs

We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic ...

0 Marthe Bonamy, et al. ∙

research

∙ 10/01/2019

Graphs of bounded cliquewidth are polynomially χ-bounded

We prove that if C is a hereditary class of graphs that is polynomially ...

0 Marthe Bonamy, et al. ∙

research

∙ 08/10/2019

Avoidable paths in graphs

We prove a recent conjecture of Beisegel et al. that for every positive ...

0 Marthe Bonamy, et al. ∙

research

∙ 08/09/2019

Shorter Labeling Schemes for Planar Graphs

An adjacency labeling scheme for a given class of graphs is an algorithm...

0 Marthe Bonamy, et al. ∙

research

∙ 04/26/2019

Every planar graph with Δ≥ 8 is totally (Δ+2)-choosable

Total coloring is a variant of edge coloring where both vertices and edg...

0 Marthe Bonamy, et al. ∙

research

∙ 04/12/2019

The Perfect Matching Reconfiguration Problem

We study the perfect matching reconfiguration problem: Given two perfect...

0 Marthe Bonamy, et al. ∙

research

∙ 11/29/2018

Graph Isomorphism for (H_1,H_2)-free Graphs: An Almost Complete Dichotomy

We consider the Graph Isomorphism problem for classes of graphs characte...

0 Marthe Bonamy, et al. ∙

research

∙ 10/15/2018

Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications

Let G be a graph with chromatic number χ, maximum degree Δ and clique nu...

0 Marthe Bonamy, et al. ∙

research

∙ 10/01/2018

Enumerating minimal dominating sets in triangle-free graphs

It is a long-standing open problem whether the minimal dominating sets o...

0 Marthe Bonamy, et al. ∙

research

∙ 03/05/2018

EPTAS for Max Clique on Disks and Unit Balls

We propose a polynomial-time algorithm which takes as input a finite set...

0 Marthe Bonamy, et al. ∙

research

∙ 02/19/2018

Distributed Recoloring

Given two colorings of a graph, we consider the following problem: can w...

0 Marthe Bonamy, et al. ∙

research

∙ 02/15/2018

Distributed coloring in sparse graphs with fewer colors

This paper is concerned with efficiently coloring sparse graphs in the d...

0 Pierre Aboulker, et al. ∙

research

∙ 07/05/2017

On Directed Feedback Vertex Set parameterized by treewidth

We study the Directed Feedback Vertex Set problem parameterized by the t...

0 Marthe Bonamy, et al. ∙

Marthe Bonamy

Featured Co-authors