Blar i Bergen Open Research Archive på forfatter "Lima, Paloma Thome de"
-
b-Coloring Parameterized by Clique-Width
Jaffke, Lars; Lima, Paloma Thome de; Lokshtanov, Daniel (Journal article; Peer reviewed, 2021)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 ... -
Structural Parameterizations of b-Coloring
Jaffke, Lars; Lima, Paloma Thome de; Sharma, Roohani (Journal article; Peer reviewed, 2023)The b-Coloring problem, which given a graph G and an integer k asks whether G has a proper k-coloring such that each color class has a vertex adjacent to all color classes except its own, is known to be FPT parameterized ... -
Taming Graphs with No Large Creatures and Skinny Ladders
Gajarský, Jakub; Jaffke, Lars; Lima, Paloma Thome de; Novotná, Jana; Pilipczuk, Marcin; Rzążewski, Paweł; Souza, Uéverton S. (Journal article; Peer reviewed, 2022)We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder ... -
Three problems on well-partitioned chordal graphs
Ahn, Jungho; Jaffke, Lars; Kwon, O-Joung; Lima, Paloma Thome de (Journal article; Peer reviewed, 2021)In this work, we solve three problems on well-partitioned chordal graphs. First, we show that every connected (resp., 2-connected) well-partitioned chordal graph has a vertex that intersects all longest paths (resp., longest ... -
Treewidth is NP-Complete on Cubic Graphs
Bodlaender, Hans L.; Bonnet, Édouard; Jaffke, Lars; Knop, Dusan; Lima, Paloma Thome de; Milanič, Martin; Ordyniak, Sebastian; Pandey, Sukanya; Suchy, Ondrey (Journal article; Peer reviewed, 2023)In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new ... -
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
Bodlaender, Hans L.; Groenland, Carla; Jacob, Hugo; Jaffke, Lars; Lima, Paloma Thome de (Journal article; Peer reviewed, 2022)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 ...