Université de Fribourg

Reducing the Domination Number of Graphs via Edge Contractions

Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - LIPICS Vol. 138, 2019, p. 41:1-41:13

In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k <= 2, the problem is coNP-hard. We further prove that for k=1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and that...

Université de Fribourg

Reducing the Domination Number of Graphs via Edge Contractions

Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2014, no. 41, p. 1-13

In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >=0? We show that for k <=2, the problem is coNP-hard. We further prove that for k = 1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and...

Public access from Mar 8, 2021
Université de Fribourg

Proper circular arc graphs as intersection graphs of pathson a grid

Galby, Esther ; Mazzoleni, María Pía ; Ries, Bernard

In: Discrete Applied Mathematics, 2019, vol. 262, p. 195-202

In this paper we present a characterization, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a grid, where each path has at most one bend (turn).

Public access from Dec 18, 2019
Université de Fribourg

On contact graphs of paths on a grid

Deniz, Zakir ; Galby, Esther ; Munaro, Andrea ; Ries, Bernard

In: Lecture Notes in Computer Science, 2018, vol. 11282, p. 317-330

In this paper we consider Contact graphs of Paths on a Grid (CPG graphs), i.e. graphs for which there exists a family of interiorly disjoint paths on a grid in one-to-one correspondence with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. Our class generalizes the well studied class of VCPG graphs (see [1]). We examine CPG...

Public access from Feb 20, 2021
Université de Fribourg

Classifying k-edge colouring for H-free graphs

Galby, Esther ; T. Lima, Paloma ; Paulusma, Daniël ; Ries, Bernard

In: Information procesing letters, 2019, vol. 146, p. 39-43

A graph is H-free if it does not contain an induced subgraph isomorphic to H. For every integer k and every graph H, we determine the computational complexity of k-Edge Colouring for H-free graphs.