23 citations · 150 across the 51 of their papers we have counts for
8 papers · 1 filter
Jones' Conjecture in subcubic graphs
Marthe Bonamy, François Dross, Tomáš Masařík +3
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain vertex-disjoint cycles, then it suffices to delete vertices to obta…
Dominating sets reconfiguration under token sliding
Marthe Bonamy, Paul Dorbec, Paul Ouvrard
Let be a graph and and be two dominating sets of of size . Does there exist a sequence of…
Graphs of bounded cliquewidth are polynomially -bounded
Marthe Bonamy, Michał Pilipczuk
We prove that if is a hereditary class of graphs that is polynomially -bounded, then the class of graphs that admit decompositions into pieces belonging to $\mathc…
Avoidable paths in graphs
Marthe Bonamy, Oscar Defrain, Meike Hatzel +1
We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises th…
Shorter Labeling Schemes for Planar Graphs
Marthe Bonamy, Cyril Gavoille, Michal Pilipczuk
An \emph{adjacency labeling scheme} for a given class of graphs is an algorithm that for every graph from the class, assigns bit strings (labels) to vertices of so that for…
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…