Esther Galby

activity

20182026

most citedOn the Parameterized Complexity of

k

-Edge Colouring

4 citations · 8 across the 12 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

math.CO2020★ 1 cited

Reducing the domination number of $P_{3} + k P_{2}$ -free graphs via one edge contraction

Esther Galby, Felix Mann, Bernard Ries

In this note, we consider the following problem: given a connected graph $G$ , can we reduce the domination number of $G$ by using only one edge contraction? We show that the proble…

cs.DM2020

Blocking total dominating sets via edge contractions

Esther Galby, Felix Mann, Bernard Ries

In this paper, we study the problem of deciding whether the total domination number of a given graph $G$ can be reduced using exactly one edge contraction (called 1-Edge Contractio…

cs.DS2020

Approximating Independent Set and Dominating Set on VPG graphs

Esther Galby, Andrea Munaro

We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain $NP$ -hard on $B_{0}$ -VPG graphs admi…

Reducing the domination number of P3​+kP2​-free graphs via one edge contraction

Blocking total dominating sets via edge contractions

Approximating Independent Set and Dominating Set on VPG graphs

Reducing the domination number of $P_{3} + k P_{2}$ -free graphs via one edge contraction