4 citations · 12 across the 12 of their papers we have counts for
22 papers
-Coloring Parameterized by Pathwidth is XNLP-complete
Lars Jaffke, Paloma T. Lima, Roohani Sharma
We show that the -Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexit…
A tight quasi-polynomial bound for Global Label Min-Cut
Lars Jaffke, Paloma T. Lima, Tomáš Masařík +2
We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (o…
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Meike Hatzel, Lars Jaffke, Paloma T. Lima +4
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph , pairs of ve…
On the maximum number of edges in planar graphs of bounded degree and matching number
Lars Jaffke, Paloma T. Lima
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.
Taming graphs with no large creatures and skinny ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima +4
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class there exists a constant such that no member of $\mathcal{G}…
Reducing the Vertex Cover Number via Edge Contractions
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +2
The CONTRACTION(vc) problem takes as input a graph on vertices and two integers and , and asks whether one can contract at most edges to reduce the size of a min…
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…
Graph Square Roots of Small Distance from Degree One Graphs
Petr A. Golovach, Paloma T. Lima, Charis Papadopoulos
Given a graph class , the task of the -Square Root problem is to decide, whether an input graph has a square root from . We are inter…
Structural Parameterizations of Clique Coloring
Lars Jaffke, Paloma T. Lima, Geevarghese Philip
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the C…
Reducing graph transversals via edge contractions
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +1
For a graph invariant , the Contraction() problem consists in, given a graph and two positive integers , deciding whether one can contract at most edges of t…
b-Coloring Parameterized by Clique-Width
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph clas…
Algorithms for the rainbow vertex coloring problem on graph classes
Paloma T. Lima, Erik Jan van Leeuwen, Marieke van der Wegen
Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow…
Well-partitioned chordal graphs: obstruction set and disjoint paths
Jungho Ahn, Lars Jaffke, O-joung Kwon +1
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the ve…
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…
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.
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
Lars Jaffke, Paloma T. Lima
A -coloring of a graph is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b…
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…
Parameterized Aspects of Strong Subgraph Closure
Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis +2
Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized…
Transversals of Longest Paths
Márcia R. Cerioli, Cristina G. Fernandes, Renzo Gómez +2
Let $\lpt(G)$ be the minimum cardinality of a set of vertices that intersects all longest paths in a graph . Let be the size of a maximum clique in , and $\tw(G)$ be t…
Finding Connected Secluded Subgraphs
Petr A. Golovach, Pinar Heggernes, Paloma Lima +1
Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough…
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch +2
Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem i…