Galby, Esther Lima, Paloma T. Ries, Bernard 2019 In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P6, P4 + P2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P3-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on H-free graphs when H is connected. application/pdf https://folia.unifr.ch/global/documents/308270 https://folia.unifr.ch/documents/308270/files/lipics-isaac-2019-21.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.ISAAC.2019.21 info:eu-repo/semantics/openAccess License undefined 30th International Symposium on Algorithms and Computation (ISAAC) - Leibniz International Proceedings in Informatics / Pinyan Lu and Guochuan Zhang. - Schloss Dagstuhl – Leibniz-Zentrum für Informatik. - 2019, vol. 149, no. 21, p. 1-14 domination number blocker problem H-free graphs info:eu-repo/classification/udc/004 Blocking Dominating Sets for H-Free Graphs via Edge Contractions http://purl.org/coar/resource_type/c_5794