4 citations · 8 across the 12 of their papers we have counts for
19 papers
Odd Cycle Transversal on -free graphs
Esther Galby, Paloma T. de Lima, Andrea Munaro +1
\textsc{Odd Cycle Transversal} is a classic -hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite…
Maximum list -colorable induced subgraphs in -free graphs
Esther Galby, Paloma T. Lima, Andrea Munaro +1
We show that, for every fixed positive integers and , \textsc{Max-Weight List -Colorable Induced Subgraph} admits a polynomial-time algorithm on -free graphs. This…
Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
Esther Galby, Andrea Munaro, Shizhou Yang
We investigate a relaxation of the notion of fractional treewidth-fragility, namely fractional tree-independence-number-fragility. In particular, we obtain polynomial-time approxim…
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
Esther Galby, Andrea Munaro, Shizhou Yang
We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for inde…
The complexity of blocking (semi)total dominating sets with edge contractions
Esther Galby
We consider the problem of reducing the (semi)total domination number of graph by one by contracting edges. It is known that this can always be done with at most three edge contrac…
Using edge contractions to reduce the semitotal domination number
Esther Galby, Paloma T. Lima, Felix Mann +1
In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting edges, for some fixed . We show that this can alway…
Reducing the domination number of -free graphs via one edge contraction
Esther Galby, Felix Mann, Bernard Ries
In this note, we consider the following problem: given a connected graph , can we reduce the domination number of by using only one edge contraction? We show that the proble…
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 can be reduced using exactly one edge contraction (called 1-Edge Contractio…
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 -hard on -VPG graphs admi…
Characterising circular-arc contact -VPG graphs
Flavia Bonomo-Braberman, Esther Galby, Carolina Lucía Gonzalez
A contact -VPG graph is a graph for which there exists a collection of nontrivial pairwise interiorly disjoint horizontal and vertical segments in one-to-one correspondence wi…
Blocking dominating sets for -free graphs via edge contractions
Esther Galby, Paloma T. Lima, Bernard Ries
In this paper, we consider the following problem: given a connected graph , can we reduce the domination number of by one by using only one edge contraction? We show that th…
Reducing the domination number of graphs via edge contractions
Esther Galby, Paloma T. Lima, Bernard Ries
In this paper, we study the following problem: given a connected graph , can we reduce the domination number of by at least one using edge contractions, for some fixed i…
CPG graphs: Some structural and hardness results
Nicolas Champseix, Esther Galby, Andrea Munaro +1
In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in [Deniz et al., 2018]. A CPG graph is a graph for which there exists a…
On the Parameterized Complexity of -Edge Colouring
Esther Galby, Paloma T. Lima, Daniël Paulusma +1
For every fixed integer , we prove that -Edge Colouring is fixed-parameter-tractable when parameterized by the number of vertices of maximum degree.
Planar CPG graphs
Nicolas Champseix, Esther Galby, Bernard Ries
We show that for any , there exists a planar graph which is -CPG but not -CPG. As a consequence, we obtain that -CPG is a strict subclass of -…
Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Esther Galby, Andrea Munaro, Bernard Ries
A semitotal dominating set of a graph with no isolated vertex is a dominating set of such that every vertex in is within distance two of another vertex in . The…
Classifying k-Edge Colouring for H-free Graphs
Esther Galby, Paloma T. Lima, Daniel Paulusma +1
A graph is -free if it does not contain an induced subgraph isomorphic to . For every integer and every graph , we determine the computational complexity of -Edge C…
Proper circular arc graphs as intersection graphs of paths on a grid
Esther Galby, Maria Pia Mazzoleni, Bernard Ries
In this paper we present a characterisation, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a…
On contact graphs of paths on a grid
Zakir Deniz, Esther Galby, Andrea Munaro +1
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 correspon…