23 citations · 150 across the 51 of their papers we have counts for
21 papers · 1 filter
Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Marthe Bonamy, Oscar Defrain, Piotr Micek +1
Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating min…
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…
Every planar graph with is totally -choosable
Marthe Bonamy, Théo Pierron, Éric Sopena
Total coloring is a variant of edge coloring where both vertices and edges are to be colored. A graph is totally -choosable if for any list assignment of colors to each vert…
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)…
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…