Publications : open access

Journal and conference versions are grouped together. If you would like to see separate lists for journal and conference publications, check dblp. Authors are ordered alphabetically in all publications, as it is usual in Theoretical Computer Science papers.

• 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
  
• 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 (to appear)   |   SODA 2024 (quasi-poly algo)   |   arXiv
  
• XNLP-completeness for parameterized problems on graphs with a linear structure
  with H. L. Bodlaender, C. Groenland, H. Jacob and L. Jaffke
  Algorithmica     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 (to appear)   |   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

• Non-empty intersection of longest paths in P_5-free and claw-free graphs (arXiv)
  with A. Nikabadi
  

Unpublished notes

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