23 citations · 150 across the 51 of their papers we have counts for
7 papers · 1 filter
A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition
Marthe Bonamy, Lukasz Kowalik
We show a kernel of at most vertices for the Planar Feedback Vertex Set problem restricted to planar graphs, i.e., a polynomial-time algorithm that transforms an input instan…
Graphs with large chromatic number induce -cycles
Marthe Bonamy, Pierre Charbit, Stéphan Thomassé
Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length have bounded chromatic number. This implies the very first case of a much bro…
The Erdős-Hajnal Conjecture for Long Holes and Anti-holes
Marthe Bonamy, Nicolas Bousquet, Stéphan Thomassé
Erdős and Hajnal conjectured that, for every graph , there exists a constant such that every graph on vertices which does not contain any induced copy of has a…
On the neighbour sum distinguishing index of planar graphs
Marthe Bonamy, Jakub Przybyło
Let be a proper edge colouring of a graph with integers . Then , while by Vizing's theorem, no more than is necessary for constru…
Reconfiguring Independent Sets in Cographs
Marthe Bonamy, Nicolas Bousquet
Two independent sets of a graph are adjacent if they differ on exactly one vertex (i.e. we can transform one into the other by adding or deleting a vertex). Let be an integer.…
Planar graphs with and no triangle adjacent to a are minimally edge and total choosable
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou
For planar graphs, we consider the problems of \emph{list edge coloring} and \emph{list total coloring}. Edge coloring is the problem of coloring the edges while ensuring that two…