Browsing Bergen Open Research Archive by Author "Lima, Paloma T."

Now showing items 1-11 of 11

    • 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 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 vertex path between every pair of its ...

    • b-Coloring Parameterized by Clique-Width 

      Jaffke, Lars; Lima, Paloma T.; Lokshtanov, Daniel (Journal article; Peer reviewed, 2023)
      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 classes, and answers open questions posed by ...

    • A complexity dichotomy for critical values of the b-chromatic number of graphs 

      Lima, Paloma T.; Jaffke, Lars (Journal article; Peer reviewed, 2020)
      A b-coloring 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 b-Coloring problem asks whether a graph G has ...

    • A complexity dichotomy for critical values of the b-chromatic number of graphs 

      Jaffke, Lars; Lima, Paloma T. (Peer reviewed; Journal article, 2019-08-20)
      A b-coloring 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 b-Coloring 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, 2020-03)
      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 ...

    • Well-partitioned chordal graphs 

      Ahn, Jungho; Jaffke, Lars; Kwon, O-joung; 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 well-partitioned chordal graphs. A connected graph G is a well-partitioned chordal graph if there exist a partition P ...

    • XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure 

      Bodlaender, Hans L.; Groenland, Carla; Jacob, Hugo; Jaffke, Lars; Lima, Paloma T. (Journal article; Peer reviewed, 2024)
      In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies ...