• 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 ...
    • 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 ...
    • 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 ...