Paloma T. de Lima

Publications

• Maximum list r-colorable induced subgraphs in kP3-free graphs
  with E. Galby, A. Munaro and A. Nikabadi
  ESA 2025   |   arXiv
• Algorithmic applications of F-branchwidth
  with B. Bergougnoux, T. Hamm and L. Jaffke
  ESA 2025
• A parameterized complexity analysis of bounded height depth-first search trees
  with L. Jaffke, W. Nadara and E. Sam
  WG 2025   |   arXiv
• Longest path transversals in P_5-free and claw-free graphs
  with A. Nikabadi
  CIAC 2025   |   arXiv
• Odd Cycle Transversal on P_5-free graphs in polynomial time
  with A. Agrawal, D. Lokshtanov, P. Rzążewski, S. Saurabh and R. Sharma
  ACM Transactions on Algorithms (2025)   |   SODA 2024 (quasi-poly algo)   |   arXiv
• On the complexity of rainbow vertex colouring diametral path graphs
  with J. Dyrseth
  Journal of Computer and System Sciences (2025)   |   ISAAC 2022
• Tree decompositions meet induced matchings: beyond Max Weight Independent Set
  with M. Milanič, P. Muršič, K. Okrasa, P. Rzążewski and K. Štorgel
  ESA 2024   |   arXiv
• XNLP-completeness for parameterized problems on graphs with a linear structure
  with H. L. Bodlaender, C. Groenland, H. Jacob and L. Jaffke
  Algorithmica (2024) Special Issue: IPEC   |   IPEC 2022 Best paper award   |   arXiv
• Taming graphs with no large creatures and skinny ladders
  with J. Gajarský, L. Jaffke, J. Novotná, Ma. Pilipczuk, P. Rzążewski and U. Souza
  SIAM Journal on Discrete Mathematics (2024)   |   ESA 2022   |   arXiv
• Structural Parameterizations of b-Coloring
  with L. Jaffke and R. Sharma
  ISAAC 2023   |   preliminary arXiv version
• Treewidth is NP-complete on cubic graphs (and related results)
  with H. Bodlaender, E. Bonnet, L. Jaffke, D. Knop, M. Milanič, S. Ordyniak, S. Pandey and O. Suchý
  IPEC 2023   |   arXiv
• Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
  with M. Hatzel, L. Jaffke, T. Masařík, Ma. Pilipczuk, R. Sharma and M. Sorge
  SODA 2023   |   HALG 2023   |   arXiv
• A tight quasi-polynomial bound for Global Label Min-Cut
  with L. Jaffke, T. Masařík, Ma. Pilipczuk and U. Souza
  SODA 2023   |   arXiv
• b-coloring parameterized by clique-width
  with L. Jaffke and D. Lokshtanov
  Theory of Computing Systems (2023) Special Issue: STACS   |   STACS 2021   |   arXiv
• Reducing the vertex cover number via edge contractions
  with V. F. dos Santos, I. Sau, U. Souza and P. Tale
  Journal of Computer and System Sciences (2023)   |   MFCS 2022   |   arXiv
  
• On the maximum number of edges in planar graphs of bounded degree and matching number
  with L. Jaffke
  Discrete Mathematics (2023)   |   arXiv
• Using edge contractions to decrease the semitotal domination number
  with E. Galby, F. Mann and B. Ries
  Theoretical Computer Science (2023)
• On the complexity of rainbow vertex colouring diametral path graphs
  with J. Dyrseth
  ISAAC 2022
• Well-partitioned chordal graphs
  with J. Ahn, L. Jaffke and O. Kwon
  Discrete Mathematics (2022)   |   WG 2020   |   CIAC 2021   |   arXiv
• Graph square roots of small distance from degree one graphs
  with P. A. Golovach and C. Papadopoulos
  Theory of Computing Systems (2022)   |   pdf   |   LATIN 2020
• On the maximum number of edges in chordal graphs of bounded degree and matching number
  with J. R. S. Blair, P. Heggernes and D. Lokshtanov
  Algorithmica (2022)   Special Issue: LATIN   |   pdf   |   LATIN 2020
• Structural parameterizations of clique coloring
  with L. Jaffke and G. Philip
  Algorithmica (2022)   |   MFCS 2020
• Algorithms for the rainbow vertex coloring problem on graph classes
  with E. J. van Leeuwen and M. van der Wegen
  Theoretical Computer Science (2021)   |   MFCS 2020
• Reducing graph transversals via edge contractions
  with V. F. dos Santos, I. Sau and U. S. Souza
  Journal of Computer and System Sciences (2021)   |   pdf   |   MFCS 2020   |   PC Newsletter
• Reducing the domination number of graphs via edge contractions and vertex deletions
  with E. Galby and B. Ries
  Discrete Mathematics (2021)   |   MFCS 2019   |   ISAAC 2019
• Finding connected secluded subgraphs
  with P. A. Golovach, P. Heggernes and P. Montealegre
  Journal of Computer and System Sciences (2020)   |   pdf   |   IPEC 2017
• Parameterized aspects of strong subgraph closure
  with P. A. Golovach, P. Heggernes, A. L. Konstantinidis and C. Papadopoulos
  Algorithmica (2020)   |   pdf   |   SWAT 2018
• A complexity dichotomy for critical values of the b-chromatic number of graphs
  with L. Jaffke
  Theoretical Computer Science (2020)   |   MFCS 2019
• Intersection of longest paths in graph classes
  with M. R. Cerioli
  Discrete Applied Mathematics (2020)   |   CTW 2016
• Transversals of longest paths
  with M. R. Cerioli, C. G. Fernandes, R. Gómez and J. Gutiérrez
  Discrete Mathematics (2020)   |   pdf   |   LAGOS 2017
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
  with P. A. Golovach, P. Heggernes, D. Kratsch and D. Paulusma
  Algorithmica (2019)   |   pdf   |   WG 2017
• Classifying k-edge colouring for H-free graphs
  with E. Galby, D. Paulusma and B. Ries
  Information Processing Letters (2019)   |   pdf
• Rainbow vertex coloring bipartite graphs and chordal graphs
  with P. Heggernes, D. Issac, J. Lauri and E. J. van Leeuwen
  MFCS 2018

Preprints

Unpublished notes

• On the parameterized complexity of k-edge colouring (arXiv)
  with E. Galby, D. Paulusma and B. Ries