Publications
Journal and conference versions are grouped together. For separate lists, check dblp.
Authors are ordered alphabetically in all publications, as it is usual in Theoretical Computer Science papers.
- 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