Browsing Bergen Open Research Archive by Author "Lima, Paloma T."
Now showing items 110 of 10

Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
Lima, Paloma T.; van Leeuwen, Erik Jan; van der Wegen, Marieke (Journal article; Peer reviewed, 2020)Given a vertexcolored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertexconnected if there is a rainbow vertex path between every pair of its ... 
bColoring Parameterized by CliqueWidth
Jaffke, Lars; Lima, Paloma T.; Lokshtanov, Daniel (Journal article; Peer reviewed, 2023)We provide a polynomialtime algorithm for b Coloring on graphs of constant cliquewidth. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by ... 
A complexity dichotomy for critical values of the bchromatic number of graphs
Lima, Paloma T.; Jaffke, Lars (Journal article; Peer reviewed, 2020)A bcoloring of a graph G 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 bColoring problem asks whether a graph G has ... 
A complexity dichotomy for critical values of the bchromatic number of graphs
Jaffke, Lars; Lima, Paloma T. (Peer reviewed; Journal article, 20190820)A bcoloring of a graph G 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 bColoring problem asks whether a graph G has ... 
On the maximum number of edges in planar graphs of bounded degree and matching number
Jaffke, Lars; Lima, Paloma T. (Journal article; Peer reviewed, 2023)We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number. 
Reducing Graph Transversals via Edge Contractions
Lima, Paloma T.; dos Santos, Vinicius F.; Sau, Ignasi; Souza, Uéverton S. (Journal article; Peer reviewed, 2020)For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least ... 
Reducing the domination number of graphs via edge contractions and vertex deletions
Galby, Esther; Lima, Paloma T.; Ries, Bernard (Journal article; Peer reviewed, 2021)In this work, 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=1 (resp. k=2), the ... 
Structural parameterizations of clique coloring
Jaffke, Lars; Lima, Paloma T.; Philip, Geevarghese (Journal article; Peer reviewed, 2020)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 Clique Coloring problem which asks whether ... 
Transversals of longest paths
Cerioli, Marcia R.; Fernandes, Cristina G.; Gómez, Renzo; Gutiérrez, Juan; Lima, Paloma T. (Journal article; Peer reviewed, 202003)Let lpt(G) be the minimum cardinality of a transversal of longest paths in G, that is, a set of vertices that intersects all longest paths in a graph G. There are several results in the literature bounding the value of ... 
Wellpartitioned chordal graphs
Ahn, Jungho; Jaffke, Lars; Kwon, Ojoung; Lima, Paloma T. (Journal article; Peer reviewed, 2022)We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call wellpartitioned chordal graphs. A connected graph G is a wellpartitioned chordal graph if there exist a partition P ...