4 citations · 6 across the 5 of their papers we have counts for
17 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…
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…