23 citations · 150 across the 51 of their papers we have counts for
9 papers · 1 filter
Frozen -colourings of bounded degree graphs
Marthe Bonamy, Nicolas Bousquet, Guillem Perarnau
Let be a graph of maximum degree and be an integer. The -recolouring graph of is the graph whose vertices are -colourings of and where two -colourings…
Graph Isomorphism for -free Graphs: An Almost Complete Dichotomy
Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski +3
We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs and for all but six pairs $(H_1,H_2)…
Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications
Marthe Bonamy, Thomas Perrett, Luke Postle
Let be a graph with chromatic number , maximum degree and clique number . Reed's conjecture states that for…
Enumerating minimal dominating sets in -free graphs and variants
Marthe Bonamy, Oscar Defrain, Marc Heinrich +2
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph cl…
The structure of binary matroids with no induced claw or Fano plane restriction
Marthe Bonamy, Frantisek Kardos, Tom Kelly +2
An 'induced restriction' of a simple binary matroid is a restriction , where is a flat of . We consider the class of all simple binary matroids co…
EPTAS for Max Clique on Disks and Unit Balls
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +2
We propose a polynomial-time algorithm which takes as input a finite set of points of and compute, up to arbitrary precision, a maximum subset with diameter at most $…