Staff profile

Chapter in book

• Maximizing Matching Cuts
  Le, V. B., Lucke, F., Paulusma, D., & Ries, B. (2024). Maximizing Matching Cuts. In P. M. Pardalos, & O. A. Prokopyev (Eds.), Encyclopedia of Optimization (1-10). Springer Nature. https://doi.org/10.1007/978-3-030-54621-2_898-1

Conference Paper

• The Complexity of Diameter on H-free Graphs
  Oostveen, J. J., Paulusma, D., & van Leeuwen, E. J. (2024, June). The Complexity of Diameter on H-free Graphs. Presented at WG 2024, Gozd Martuljek, Slovenia
• Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs,
  Lucke, F., Momeni, A., Paulusma, D., & Smith, S. (2024, June). Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs,. Presented at WG 2024, Gozd Martuljek, Slovenia
• Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs
  Lozin, V. V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., & van Leeuwen, E. J. (2024, December). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. Presented at ISAAC, ISAAC 2024
• Complexity framework for forbidden subgraphs IV: The Steiner Forest problem
  Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. .., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, July). Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Presented at IWOCA, Ischia, Italy
• Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs
  Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, June). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Presented at SWAT 2024, Helsinki, Finland
• Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded
  Benedek, M., Biró, P., Csáji, G., Johnson, M., Paulusma, D., & Ye, X. (2024, May). Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded. Presented at AAMAS, Auckland, New Zealand
• Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
  Lucke, F., Paulusma, D., & Ries, B. (2023, August). Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France
• Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
  Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023, August). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France
• Matching cuts in graphs of high girth and H-free graphs
  Feghali, C., Lucke, F., Paulusma, D., & Ries, B. (2023, December). Matching cuts in graphs of high girth and H-free graphs. Presented at ISAAC 2023
• Computing Subset Vertex Covers in H-Free Graphs
  Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., & van Leeuwen, E. J. (2023, September). Computing Subset Vertex Covers in H-Free Graphs. Presented at FCT 2023: Fundamentals of Computation Theory, Trier, Germany
• Computing Balanced Solutions for Large International Kidney Exchange Schemes
  Benedek, M., Biró, P., Kern, W., & Paulusma, D. (2022, May). Computing Balanced Solutions for Large International Kidney Exchange Schemes. Presented at AAMAS ' 22: International Conference on Autonomous Agents and Multi-Agent Systems, Virtual Event / New Zealand
• Finding matching cuts in H-free graphs
  Lucke, F., Paulusma, D., & Ries, B. (2021, December). Finding matching cuts in H-free graphs. Presented at 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Seoul, South Korea
• Classifying Subset Feedback Vertex Set for H-free graphs
  Paesani, G., Paulusma, D., & Rzążewski, P. (2022, December). Classifying Subset Feedback Vertex Set for H-free graphs. Presented at WG 2022
• Few induced disjoint paths for H-free graphs
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022, May). Few induced disjoint paths for H-free graphs. Presented at ISCO 2022, Online
• Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
• The Complexity of L(p,q)-Edge-Labelling
  Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022, March). The Complexity of L(p,q)-Edge-Labelling. Presented at The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), University of Jember, East Java
• An algorithmic framework for locally constrained homomorphisms
  Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2022, December). An algorithmic framework for locally constrained homomorphisms. Presented at WG 2022
• Injective colouring for H-free graphs
  Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2023, June). Injective colouring for H-free graphs. Presented at CSR 2021, Sochi
• Steiner trees for hereditary graph classes
  Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2020, May). Steiner trees for hereditary graph classes. Presented at LATIN 2020, São Paulo
• Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs
  Paesani, G., Paulusma, D., & Rzążewski, P. (2021, August). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs. Presented at MFCS 2021, Tallinn, Estonia
• Acyclic, star and injective colouring: bounding the diameter
  Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. Acyclic, star and injective colouring: bounding the diameter
• Partitioning H-free graphs of bounded diameter
  Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021, December). Partitioning H-free graphs of bounded diameter. Presented at 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan
• Colouring graphs of bounded diameter in the absence of small cycles
  Martin, B., Paulusma, D., & Smith, S. (2021, May). Colouring graphs of bounded diameter in the absence of small cycles. Presented at CIAC 2021, Virtual Event
• Computing weighted subset transversals in H-free graphs
  Brettell, N., Johnson, M., & Paulusma, D. (2021, August). Computing weighted subset transversals in H-free graphs. Presented at WADS 2021, Halifax, Nova Scotia
• QCSP on reflexive tournaments
  Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021, September). QCSP on reflexive tournaments. Presented at The 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon / Online
• Disjoint paths and connected subgraphs for H-free graphs
  Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Disjoint paths and connected subgraphs for H-free graphs
• Solving problems on generalized convex graphs via mim-width
  Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. Solving problems on generalized convex graphs via mim-width
• Computing subset transversals in H-free graphs
  Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020, December). Computing subset transversals in H-free graphs. Presented at WG 2020, Leeds, England
• Clique-Width: Harnessing the Power of Atoms
  Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2020, June). Clique-Width: Harnessing the Power of Atoms. Presented at WG 2020, Leeds, England
• Bounding the mim-width of hereditary graph classes
  Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2020, December). Bounding the mim-width of hereditary graph classes. Presented at IPEC 2020
• Contracting to a longest path in H-free graphs
  Kern, W., & Paulusma, D. (2020, December). Contracting to a longest path in H-free graphs. Presented at ISAAC 2020, Hong Kong, China
• Acyclic, star and injective colouring: a complexity picture for H-free graphs
  Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020, September). Acyclic, star and injective colouring: a complexity picture for H-free graphs. Presented at ESA 2020, Pisa, Italy (Virtual Event)
• Colouring H-free graphs of bounded diameter
  Martin, B., Paulusma, D., & Smith, S. (2019, August). Colouring H-free graphs of bounded diameter. Presented at MFCS 2019, Aachen, Germany
• Tree pivot-minors and linear rank-width
  Dabrowski, K., Dross, F., Jeong, J., Kanté, M., Kwon, O., Oum, S., & Paulusma, D. (2019, July). Tree pivot-minors and linear rank-width. Presented at EuroComb 2019, Bratislava, Slovakia
• Independent transversals versus transversals
  Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019, December). Independent transversals versus transversals. Presented at EuroComb 2019, Bratislava, Slovakia
• On cycle transversals and their connected variants in the absence of a small linear forest
  Feghali, C., Johnson, M., Paesani, G., & Paulusma, D. (2019, August). On cycle transversals and their connected variants in the absence of a small linear forest. Presented at FCT 2019, Copenhagen, Denmark
• Generalized matching games for international kidney exchange
  Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (2019, December). Generalized matching games for international kidney exchange. Presented at AAMAS 2019, Montreal, Canada
• Finding a small number of colourful components
  Bulteau, L., Dabrowski, K., Fertin, G., Johnson, M., Paulusma, D., & Vialette, S. (2019, December). Finding a small number of colourful components. Presented at CPM 2019, Pisa, Italy
• Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
  Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019, December). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Presented at WADS 2019, Edmonton, Canada
• Colouring (Pr+Ps)-free graphs
  Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2018, December). Colouring (Pr+Ps)-free graphs. Presented at 29th International Symposium on Algorithms and Computation (ISAAC 2018)., Jiaoxi, Yilan County, Taiwan
• Connected Vertex Cover for (sP1+P5)-free graphs
  Johnson, M., Paesani, G., & Paulusma, D. (2018, June). Connected Vertex Cover for (sP1+P5)-free graphs. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany
• Computing small pivot-minors
  Dabrowski, K. K., Dross, F., Jeong, J., Kanté, M. M., Kwon, O., Oum, S., & Paulusma, D. (2018, June). Computing small pivot-minors. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany
• Simple games versus weighted voting games
  Hof, F., Kern, W., Kurz, S., & Paulusma, D. (2018, September). Simple games versus weighted voting games. Presented at 11th International Symposium on Algorithmic Game Theory (SAGT 2018)., Beijing, China
• Colouring Square-Free Graphs without Long Induced Paths
  Gaspers, S., Huang, S., & Paulusma, D. (2023, February). Colouring Square-Free Graphs without Long Induced Paths. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France
• Surjective H-Colouring over Reflexive Digraphs
  Larose, B., Martin, B., & Paulusma, D. (2023, February). Surjective H-Colouring over Reflexive Digraphs. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France
• On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
  Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018, August). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. Presented at 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK
• Disconnected Cuts in Claw-free Graphs
  Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018, August). Disconnected Cuts in Claw-free Graphs. Presented at 26th Annual European Symposium on Algorithms (ESA 2018)., Helsinki, Finland
• Clique-Width for Graph Classes Closed under Complementation
  Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017, August). Clique-Width for Graph Classes Closed under Complementation. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark
• Recognizing Graphs Close to Bipartite Graphs
  Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017, August). Recognizing Graphs Close to Bipartite Graphs. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark
• Clique-width and well-quasi ordering of triangle-free graph classes
  Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017, June). Clique-width and well-quasi ordering of triangle-free graph classes. Presented at WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, Eindhoven, The Netherlands
• Reducing the chromatic number by vertex or edge deletions
  Picouleau, C., Paulusma, D., & Ries, B. Reducing the chromatic number by vertex or edge deletions. Presented at LAGOS 2017: The IX Latin and American Algorithms, Graphs and Optimization Symposium., Marseille, France
• Contracting bipartite graphs to paths and cycles
  Dabrowski, K., & Paulusma, D. Contracting bipartite graphs to paths and cycles. Presented at Eurocomb 2017: European Conference on Combinatorics, Graph Theory and Applications., Vienna, Austria
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
  Golovach, P., Heggernes, P., Kratsch, D., Lima, P., & Paulusma, D. (2017, June). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Presented at 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2017), Eindhoven, The Netherlands
• Surjective H-Colouring: new hardness results
  Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017, June). Surjective H-Colouring: new hardness results. Presented at Computability in Europe (CiE 2017)., Turku, Finland
• Blocking independent sets for H-free graphs via edge contractions and vertex deletions
  Paulusma, D., Picouleau, C., & Ries, B. (2017, April). Blocking independent sets for H-free graphs via edge contractions and vertex deletions. Presented at Theory and applications of models of computation, 14th Annual Conference, TAMC 2017, Bern, Switzerland
• Independent Feedback Vertex Set for P5-free Graphs
  Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017, December). Independent Feedback Vertex Set for P5-free Graphs. Presented at ISAAC 2017
• Squares of low clique number
  Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. Squares of low clique number. Presented at 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16), Gargnano, Italy
• Reducing the clique and chromatic number via edge contractions and vertex deletions
  Paulusma, D., Picouleau, C., & Ries, B. (2016, May). Reducing the clique and chromatic number via edge contractions and vertex deletions. Presented at 4th International Symposium on Combinatorial Optimization (ISCO 2016), Vietri sul Mare, Italy
• Well-quasi-ordering versus clique-width: new results on bigenic classes
  Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016, August). Well-quasi-ordering versus clique-width: new results on bigenic classes. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland
• Finding cactus roots in polynomial time
  Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016, August). Finding cactus roots in polynomial time. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland
• The stable fixtures problem with payments
  Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2015, June). The stable fixtures problem with payments. Presented at 41 International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany
• Open problems on graph coloring for special graph classes
  Paulusma, D. (2015, June). Open problems on graph coloring for special graph classes. Presented at 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Munich, Germany
• Using contracted solution graphs for solving reconfiguration problems
  Bonsma, P., & Paulusma, D. (2016, August). Using contracted solution graphs for solving reconfiguration problems. Presented at 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Krakow, Poland
• Colouring diamond-free graphs
  Dabrowski, K. K., Dross, F., & Paulusma, D. (2016, June). Colouring diamond-free graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland
• A linear kernel for finding square roots of almost planar graphs
  Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016, June). A linear kernel for finding square roots of almost planar graphs. Presented at 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland
• Filling the complexity gaps for colouring planar and bounded degree graphs
  Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2015, October). Filling the complexity gaps for colouring planar and bounded degree graphs. Presented at 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Verona, Italy
• What graphs are 2-dot product graphs?
  Johnson, M., van Leeuwen, E., & Paulusma, D. (2015, November). What graphs are 2-dot product graphs?. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway
• Kempe equivalence of colourings of cubic graphs
  Feghali, C., Johnson, M., & Paulusma, D. (2015, November). Kempe equivalence of colourings of cubic graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway
• Bounding the clique-width of H-free split graphs
  Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015, November). Bounding the clique-width of H-free split graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway
• The price of connectivity for cycle transversals
  Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2015, August). The price of connectivity for cycle transversals. Presented at 40th International Symposium, MFCS 2015, Milan, Italy
• Bounding the Clique-Width of H-free Chordal Graphs
  Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015, August). Bounding the Clique-Width of H-free Chordal Graphs. Presented at 40th International Symposium, MFCS 2015, Milan, Italy
• Minimal disconnected cuts in planar graphs
  Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. M. (2015, August). Minimal disconnected cuts in planar graphs. Presented at 20th International Symposium, FCT 2015, Gdańsk, Poland
• Editing to a planar graph of given degrees
  Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2015, June). Editing to a planar graph of given degrees
• Clique-width of graph classes defined by two forbidden induced subgraphs
  Dabrowski, K. K., & Paulusma, D. (2015, March). Clique-width of graph classes defined by two forbidden induced subgraphs. Presented at 9th International Conference on Algorithms and Complexity (CIAC 2015), Paris, France
• Contraction blockers for graphs with forbidden induced paths
  Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2015, March). Contraction blockers for graphs with forbidden induced paths. Presented at 9th International Conference on Algorithms and Complexity (CIAC 2015), Paris, France
• Bounding clique-width via perfect graphs
  Dabrowski, K. K., Huang, S., & Paulusma, D. (2015, March). Bounding clique-width via perfect graphs. Presented at International Conference on Language and Automata Theory and Applications, Nice, France
• Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
  Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2014, December). Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary
• Classifying the Clique-Width of H-Free Bipartite Graphs
  Dabrowski, K. K., & Paulusma, D. (2014, December). Classifying the Clique-Width of H-Free Bipartite Graphs. Presented at 20th International Conference, COCOON 2014, Atlanta, GA, USA
• Knocking Out P_k-free Graphs
  Johnson, M., Paulusma, D., & Stewart, A. (2014, December). Knocking Out P_k-free Graphs. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary
• Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs
  Huang, S., Johnson, M., & Paulusma, D. (2014, December). Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs. Presented at 10th International Conference, AAIM 2014, Vancouver, BC, Canada
• Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
  Golovach, P., Paulusma, D., & van Leeuwen, E. (2014, December). Induced Disjoint Paths in Circular-Arc Graphs in Linear Time. Presented at 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France
• A Reconfigurations Analogue of Brooks’ Theorem
  Feghali, C., Johnson, M., & Paulusma, D. (2014, December). A Reconfigurations Analogue of Brooks’ Theorem. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary
• Finding Shortest Paths Between Graph Colourings
  Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2014, December). Finding Shortest Paths Between Graph Colourings. Presented at 9th International Symposium, IPEC 2014, Wroclaw, Poland
• Editing to Eulerian Graphs
  Dabrowski, K. K., Golovach, P. A., Hof, V. P., & Paulusma, D. (2014, December). Editing to Eulerian Graphs. Presented at 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), Budapest, Hungary
• Sparse Square Roots
  Cochefert, M., Couturier, J.-F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2013, December). Sparse Square Roots. Presented at 39th International Workshop, WG 2013, Lübeck, Germany
• Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
  Dabrowski, K. K., Golovach, P. A., & Paulusma, D. (2013, December). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Presented at 39th International Workshop, WG 2013, Lübeck, Germany
• Model counting for CNF formuals of bounded module treewidth
  Paulusma, D., Slivovksy, F., & Szeider, S. (2013, December). Model counting for CNF formuals of bounded module treewidth. Presented at 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Kiel, Christian-Albrechts-Universität zu Kiel, Germany
• Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs
  Johnson, M., Paulusma, D., & van Leeuwen, E. (2013, December). Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. Presented at 24th International Symposium, ISAAC 2013, Hong Kong, China,
• The price of connectivity for feedback vertex set
  Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2013, December). The price of connectivity for feedback vertex set. Presented at 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013, Pisa, Italy
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
  Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2013, December). Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. Presented at 8th International Symposium, IPEC 2013, Sophia Antipolis, France
• Graph editing to a fixed target
  Golovach, P., Paulusma, D., & Stewart, I. A. (2013, December). Graph editing to a fixed target. Presented at International Workshop on Combinatorial Algorithms, Rouen, France
• Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
  Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesar, M. (2013, December). Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree. Presented at Liverpool, UK, 19th International Symposium, FCT 2013
• List Coloring in the Absence of Two Subgraphs
  Golovach, P. A., & Paulusma, D. (2013, December). List Coloring in the Absence of Two Subgraphs. Presented at 8th International Conference, CIAC 2013, Barcelona, Spain
• Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
  Broersma, H. J., Fiala, J., Golovach, P. A., Kaiser, T., Paulusma, D., & Proskurowski, A. (2013, December). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Presented at 39th International Workshop, WG 2013, 19-21 June 2013
• Solutions for the stable rommates problem with payments
  Biró, P., Bomhoff, M., Golovach, P. A., Kern, W., & Paulusma, D. (2012, December). Solutions for the stable rommates problem with payments
• How to eliminate a graph
  Golovach, P., Heggernes, P., van 't Hof, P., Manne, F., Paulusma, D., & Pilipczuk, M. (2012, December). How to eliminate a graph
• Obtaining planarity by contracting few edges
  Golovach, P. A., van 't Hog, P., & Paulusma, D. (2012, December). Obtaining planarity by contracting few edges
• Characterizing graphs of small carving-width
  Belmonte, R., van 't Hof, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012, December). Characterizing graphs of small carving-width
• Coloring graphs characterized by a forbidden subgraph
  Golovach, P. A., Paulusma, D., & Ries, B. (2012, December). Coloring graphs characterized by a forbidden subgraph
• Detecting induced minors in AT-free graphs
  Golovach, P. A., Kratsch, D., & Paulusma, D. (2012, December). Detecting induced minors in AT-free graphs
• Closing complexity gaps for coloring problems on H-free graphs
  Golovach, P. A., Paulusma, D., & Song, J. (2012, December). Closing complexity gaps for coloring problems on H-free graphs
• Finding vertex-surjective graph homomorphisms
  Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012, December). Finding vertex-surjective graph homomorphisms
• 4-Coloring H-free graphs when H is small
  Golovach, P., Paulusma, D., & Song, J. (2012, December). 4-Coloring H-free graphs when H is small
• Induced disjoint paths in claw-free graphs
  Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012, December). Induced disjoint paths in claw-free graphs
• Induced disjoint paths in AT-free graphs
  Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012, December). Induced disjoint paths in AT-free graphs
• Lift Contractions
  Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. Lift Contractions
• On the diameter of reconfiguration graphs for vertex colourings
  Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. On the diameter of reconfiguration graphs for vertex colourings
• Computing vertex-surjective homomorphisms to partially reflexive trees
  Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Computing vertex-surjective homomorphisms to partially reflexive trees. Presented at 6th International Computer Science Symposium in Russia, CSR 2011., St Petersburg, Russia
• List coloring in the absence of a linear forest
  Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011, December). List coloring in the absence of a linear forest. Presented at 37th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic
• Coloring graphs without short cycles and long induced paths
  Golovach, P. A., Paulusma, D., & Song, J. (2011, December). Coloring graphs without short cycles and long induced paths. Presented at Fundamentals of Computation Theory, 18th International Symposium, FCT 2011, Oslo, Norway
• Increasing the Minimum Degree of a Graph by Contractions
  Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2011, September). Increasing the Minimum Degree of a Graph by Contractions. Presented at IPEC 2011: Parameterized and Exact Computation, Saarbrücken, Germany
• Contracting a chordal graph to a split graph or a tree
  Golovach, P. A., Kaminski, M., & Paulusma, D. (2011, December). Contracting a chordal graph to a split graph or a tree. Presented at 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011, Warsaw, Poland
• Satisfiability of acyclic and almost acyclic CNF formulas (II)
  Ordyniak, S., Paulusma, D., & Szeider, S. (2011, December). Satisfiability of acyclic and almost acyclic CNF formulas (II). Presented at 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011, Ann Arbor, MI
• Computing Role Assignments of Proper Interval Graphs in Polynomial Time
  Heggernes, P., Hof, V. P., & Paulusma, D. (2011, December). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. Presented at 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, London
• The computational complexity of Disconnected Cut and 2K2-Partition
  Martin, B., & Paulusma, D. (2011, December). The computational complexity of Disconnected Cut and 2K2-Partition. Presented at Principles and Practice of Constraint Programming, 17th International Conference, CP 2011, Perugia, Italy
• Finding contractions and induced minors in chordal graphs via disjoint paths
  Belmonte, R., Golovach, P. A., Heggernes, P., Hof van 't, P., Kaminski, M., & Paulusma, D. (2011, December). Finding contractions and induced minors in chordal graphs via disjoint paths. Presented at 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan
• Satisfiability of Acyclic and Almost Acyclic CNF Formulas
  Ordyniak, S., Paulusma, D., & Szeider, S. (2010, December). Satisfiability of Acyclic and Almost Acyclic CNF Formulas. Presented at IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), Chennai, India
• Obtaining online ecological colourings by generalizing first-fit
  Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010, December). Obtaining online ecological colourings by generalizing first-fit. Presented at 5th International Computer Science Symposium in Russia (CSR 2010), Kazan, Russia
• Packing bipartite graphs with covers of complete bipartite graphs
  Chalopin, J., & Paulusma, D. (2010, December). Packing bipartite graphs with covers of complete bipartite graphs. Presented at 7th International Conference on Algorithms and Complexity, Rome, Italy
• L(2,1,1)-labeling is NP-complete for trees
  Golovach, P. A., Lidicky, B., & Paulusma, D. (2010, December). L(2,1,1)-labeling is NP-complete for trees. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic
• Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs
  Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010, June). Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs. Presented at WG 2010: Graph-Theoretic Concepts in Computer Science, Zarós, Crete, Greece
• On contracting graphs to fixed pattern graphs
  't, H. P. V., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010, December). On contracting graphs to fixed pattern graphs. Presented at 36th Conference on Current Trends in Theory and Practice of Computer Science, Špindleruv Mlýn, Czech Republic
• On Coloring Graphs without Induced Forests
  Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010, December). On Coloring Graphs without Induced Forests. Presented at ISAAC 2010: Algorithms and Computation, Jeju Island, Korea
• On solution concepts for matching games
  Biro, P., Kern, W., & Paulusma, D. (2010, December). On solution concepts for matching games. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic
• Contractions of planar graphs in polynomial time
  Kaminski, M., Paulusma, D., & Thilikos, D. (2010, December). Contractions of planar graphs in polynomial time. Presented at The 18th Annual European Symposium
• The k-in-a-path problem for claw-free graphs
  Fiala, J., Kaminski, M., Lidicky, B., & Paulusma, D. (2010, December). The k-in-a-path problem for claw-free graphs. Presented at 27th International Symposium on Theoretical Aspects of Computer Science, Nancy, France
• Path factors and parallel knock-out schemes of almost claw-free graphs
  Johnson, M., Paulusma, D., & Wood, C. (2010, December). Path factors and parallel knock-out schemes of almost claw-free graphs. Presented at 19th International Workshop on Combinatorial Algorithms, Nagoya
• Parameterizing cut sets in a graph by the number of their components
  Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009, December). Parameterizing cut sets in a graph by the number of their components. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States
• Induced packing of odd cycles in a planar graph
  Golovach, P. A., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009, December). Induced packing of odd cycles in a planar graph. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States
• On partitioning a graph into two connected subgraphs
  Paulusma, D., & Rooij van, J. M. M. (2009, December). On partitioning a graph into two connected subgraphs. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States
• Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs
  Broersma, H. J., Fomin, F. V., Hof van 't, P., & Paulusma, D. (2009, June). Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France
• Finding Induced Paths of Given Parity in Claw-Free Graphs
  Hof van 't, P., Kaminski, M., & Paulusma, D. (2009, December). Finding Induced Paths of Given Parity in Claw-Free Graphs. Presented at 35th International Workshop on Graph-Theoretic Concepts in Computer Science, Montpellier, France
• Three complexity results on coloring Pk-free graphs
  Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2023, June). Three complexity results on coloring Pk-free graphs. Presented at 20th International Workshop on Combinatorial Algorithms (IWOCA 2009), Hradec nad Moravicí, Czech Republic
• Computing role assignments of chordal graphs
  Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009, September). Computing role assignments of chordal graphs. Presented at 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), Wroclaw, Poland
• Partitioning graphs into connected parts
  Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009, August). Partitioning graphs into connected parts. Presented at Fourth International Computer Science Symposium in Russia (CSR 2009)., Novosibirsk, Russia
• A new characterization of P6-free graphs
  Hof, P. V., & Paulusma, D. (2008, December). A new characterization of P6-free graphs. Presented at 14th Annual International Computing and Combinatorics Conference, Dalian, China
• Comparing universal covers in polynomial time
  Fiala, J., & Paulusma, D. (2008, December). Comparing universal covers in polynomial time. Presented at 3rd International Computer Science Symposium in Russia, Moscow, Russia
• Computing sharp 2-factors in claw-free graphs
  Broersma, H. J., & Paulusma, D. (2008, December). Computing sharp 2-factors in claw-free graphs. Presented at 33th International Symposium on Mathematical Foundations of Computer Science, Toru´n, Poland
• On components of 2-factors in claw-free graphs
  Broersma, H., Paulusma, D., & Yoshimoto, K. On components of 2-factors in claw-free graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications
• Covering Graphs with Few Complete Bipartite Subgraphs
  Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2007, December). Covering Graphs with Few Complete Bipartite Subgraphs. Presented at FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, New Delhi, India
• Upper Bounds and Algorithms for Parallel Knock-Out Numbers
  Broersma, H., Johnson, M., & Paulusma, D. (2007, June). Upper Bounds and Algorithms for Parallel Knock-Out Numbers. Presented at SIROCCO 2007: Structural Information and Communication Complexity, Castiglioncello, Italy
• Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars
  Broersma, H., Marchal, B., Paulusma, D., & Salman, A. (2007, January). Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars. Presented at SOFSEM 2007, Harrachov, Czech Republic
• The computational complexity of the parallel knock-out problem
  Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006, March). The computational complexity of the parallel knock-out problem. Presented at 7th Latin American Theoretical Informatics Symposium (LATIN 2006), Valdivia, Chile
• Graph Labelings Derived from Models in Distributed Computing
  Chalopin, J., & Paulusma, D. (2006, June). Graph Labelings Derived from Models in Distributed Computing. Presented at WG 2006: Graph-Theoretic Concepts in Computer Science, Bergen, Norway
• On-line coloring of H-free bipartite graphs.
  Broersma, H. J., Capponi, A., & Paulusma, D. (2006, May). On-line coloring of H-free bipartite graphs. Presented at 6th Italian Conference on Algorithms and Complexity (CIAC 2006)., Rome, Italy
• Matrix and graph orders derived from locally constrained graph homomorphisms
  Fiala, J., Paulusma, D., & Telle, J. A. (2023, August). Matrix and graph orders derived from locally constrained graph homomorphisms. Presented at 30th International Symposium on Mathematical Foundations of Computer Science : MFCS 2005, Gdansk, Poland
• Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms
  Fiala, J., Paulusma, D., & Telle, J. (2005, June). Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms. Presented at WG 2005: Graph-Theoretic Concepts in Computer Science, Metz, France
• The Computational Complexity of the Minimum Weight Processor Assignment Problem
  Broersma, H., Paulusma, D., Smit, G., Vlaardingerbroek, F., & Woeginger, G. (2004, June). The Computational Complexity of the Minimum Weight Processor Assignment Problem. Presented at WG 2004: Graph-Theoretic Concepts in Computer Science, Bad Honnef, Germany
• Run-time assignment of tasks to multiple heterogeneous processors
  Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004, December). Run-time assignment of tasks to multiple heterogeneous processors. Presented at 5th PROGRESS Symposium on Embedded Systems., Nieuwegein, The Netherlands
• Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture
  Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004, December). Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture. Presented at Proceedings. 2004 IEEE International Conference on Field- Programmable Technology (IEEE Cat. No.04EX921)
• The Computational Complexity of the Role Assignment Problem
  Fiala, J., & Paulusma, D. (2003, June). The Computational Complexity of the Role Assignment Problem. Presented at ICALP 2003: Automata, Languages and Programming, Eindhoven, The Netherlands
• The complexity of graph contractions
  Levin, A., Paulusma, D., & Woeginger, G. (2003, June). The complexity of graph contractions. Presented at WG 2003: Graph-Theoretic Concepts in Computer Science, Elspeet, The Netherlands

Journal Article

• Partitioned matching games for international kidney exchange
  Benedek, M., Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (online). Partitioned matching games for international kidney exchange. Mathematical Programming, https://doi.org/10.1007/s10107-025-02200-9
• Clique-width for hereditary graph classes
  Dabrowski, K., Johnson, M., & Paulusma, D. (online). Clique-width for hereditary graph classes. https://doi.org/10.1017/9781108649094.002
• Matching Cuts in Graphs of High Girth and H-Free Graphs
  Feghali, C., Lucke, F., Paulusma, D., & Ries, B. (online). Matching Cuts in Graphs of High Girth and H-Free Graphs. Algorithmica, https://doi.org/10.1007/s00453-025-01318-8
• Acyclic, star and injective colouring: A complexity picture for H-free graphs
  Bok, J., Jedličková, N., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2025). Acyclic, star and injective colouring: A complexity picture for H-free graphs. Journal of Computer and System Sciences, 154, Article 103662. https://doi.org/10.1016/j.jcss.2025.103662
• Comparing width parameters on graph classes
  Brettell, N., Munaro, A., Paulusma, D., & Yang, S. (2025). Comparing width parameters on graph classes. European Journal of Combinatorics, 127, Article 104163. https://doi.org/10.1016/j.ejc.2025.104163
• Computing subset vertex covers in H-free graphs
  Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., Rauch, J., & van Leeuwen, E. J. (2025). Computing subset vertex covers in H-free graphs. Theoretical Computer Science, 1032, Article 115088. https://doi.org/10.1016/j.tcs.2025.115088
• Complexity Framework for Forbidden Subgraphs I: The Framework
  Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs I: The Framework. Algorithmica, 87(3), 429-464. https://doi.org/10.1007/s00453-024-01289-2
• Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius
  Lucke, F., Paulusma, D., & Ries, B. (2024). Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius. Theoretical Computer Science, 1017, Article 114795. https://doi.org/10.1016/j.tcs.2024.114795
• Computing balanced solutions for large international kidney exchange schemes
  Benedek, M., Biró, P., Paulusma, D., & Ye, X. (2024). Computing balanced solutions for large international kidney exchange schemes. Autonomous Agents and Multi-Agent Systems, 38(1), Article 18. https://doi.org/10.1007/s10458-024-09645-w
• An Algorithmic Framework for Locally Constrained Homomorphisms
  Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2024). An Algorithmic Framework for Locally Constrained Homomorphisms. SIAM Journal on Discrete Mathematics, 38(2), 1315-1350. https://doi.org/10.1137/22M1513290
• On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
  Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2024). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. European Journal of Combinatorics, 117, Article 103821. https://doi.org/10.1016/j.ejc.2023.103821
• Solving problems on generalized convex graphs via mim-width
  Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. (2024). Solving problems on generalized convex graphs via mim-width. Journal of Computer and System Sciences, 140, Article 103493. https://doi.org/10.1016/j.jcss.2023.103493
• Clique‐width: Harnessing the power of atoms
  Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2023). Clique‐width: Harnessing the power of atoms. Journal of Graph Theory, 104(4), 769-810. https://doi.org/10.1002/jgt.23000
• The Complexity of L(p, q)-Edge-Labelling
  Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, 85(11), 3406-3429. https://doi.org/10.1007/s00453-023-01120-4
• Finding Matching Cuts in H-Free Graphs
  Lucke, F., Paulusma, D., & Ries, B. (2023). Finding Matching Cuts in H-Free Graphs. Algorithmica, 85(10), 3290-3322. https://doi.org/10.1007/s00453-023-01137-9
• Few induced disjoint paths for H-free graphs
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024
• The Complexity of Matching Games: A Survey
  Benedek, M., Biro, P., Johnson, M., Paulusma, D., & Ye, X. (2023). The Complexity of Matching Games: A Survey. Journal of Artificial Intelligence Research, 77, 459-485. https://doi.org/10.1613/jair.1.14281
• Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z
• Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter
  Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034
• Partitioning H-free graphs of bounded diameter
  Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009
• Computing weighted subset odd cycle transversals in H-free graphs
  Brettell, N., Johnson, M., & Paulusma, D. (2022). Computing weighted subset odd cycle transversals in H-free graphs. Journal of Computer and System Sciences, 128, 71-85. https://doi.org/10.1016/j.jcss.2022.03.002
• QCSP on reflexive tournaments
  Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069
• Colouring graphs of bounded diameter in the absence of small cycles
  Martin, B., Paulusma, D., & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026
• Hard problems that quickly become very easy
  Martin, B., Paulusma, D., & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters, 174, https://doi.org/10.1016/j.ipl.2021.106213
• Induced disjoint paths in AT-free graphs
  Golovach, P., Paulusma, D., & van Leeuwen, E. (2022). Induced disjoint paths in AT-free graphs. Journal of Computer and System Sciences, 124, 170-191. https://doi.org/10.1016/j.jcss.2021.10.003
• Computing subset transversals in H-free graphs
  Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2022). Computing subset transversals in H-free graphs. Theoretical Computer Science, 902, 76-92. https://doi.org/10.1016/j.tcs.2021.12.010
• Disjoint paths and connected subgraphs for H-free graphs
  Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science, 898, 59-68. https://doi.org/10.1016/j.tcs.2021.10.019
• On the complexity of matching cut for graphs of bounded radius and H-free graphs
  Lucke, F., Paulusma, D., & Ries, B. (2022). On the complexity of matching cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science, 936, 33-42. https://doi.org/10.1016/j.tcs.2022.09.014
• Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs
  Paesani, G., Paulusma, D., & Rzążwski, P. (2022). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs. SIAM Journal on Discrete Mathematics, 36(4), 2453-2472. https://doi.org/10.1137/22m1468864
• Acyclic, Star, and Injective Colouring: Bounding the diameter
  Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2), https://doi.org/10.37236/10738
• Bounding the mim-width of hereditary graph classes
  Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2022). Bounding the mim-width of hereditary graph classes. Journal of Graph Theory, 99(1), 117-151. https://doi.org/10.1002/jgt.22730
• List k-colouring P-free graphs: a mim-width perspective
  Brettell, N., Horsfield, J., Munaro, A., & Paulusma, D. (2022). List k-colouring P-free graphs: a mim-width perspective. Information Processing Letters, 173, Article 106168. https://doi.org/10.1016/j.ipl.2021.106168
• Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration
  Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2021). Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration. Journal of Graph Theory, 98(1), 81-109. https://doi.org/10.1002/jgt.22683
• Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
  Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. (2021). Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. Theoretical Computer Science, 867, 30-39. https://doi.org/10.1016/j.tcs.2021.03.012
• What graphs are 2-dot product graphs?
  Johnson, M., Paulusma, D., & van Leeuwen, E. (2021). What graphs are 2-dot product graphs?. International Journal of Computational Geometry and Applications, 31(01), 1-16. https://doi.org/10.1142/s0218195921500011
• Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
  Bonamy, M., Bousquet, N., Dabrowski, K., Johnson, M., Paulusma, D., & Pierron, T. (2021). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Algorithmica, 83(3), 822-852. https://doi.org/10.1007/s00453-020-00747-x
• Tree pivot-minors and linear rank-width
  Dabrowski, K., Dross, F., Jeong, J., Kante, M., Kwon, O., Oum, S., & Paulusma, D. (2021). Tree pivot-minors and linear rank-width. SIAM Journal on Discrete Mathematics, 35(4), 2922-2945. https://doi.org/10.1137/21m1402339
• Disconnected cuts in claw-free graphs
  Martin, B., Paulusma, D., & van Leeuwen, E. (2020). Disconnected cuts in claw-free graphs. Journal of Computer and System Sciences, 113, 60-75. https://doi.org/10.1016/j.jcss.2020.04.005
• Colouring (Pr + Ps)-Free Graphs
  Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2020). Colouring (Pr + Ps)-Free Graphs. Algorithmica, 82(7), 1833-1858. https://doi.org/10.1007/s00453-020-00675-w
• Simple games versus weighted voting games: bounding the critical threshold value
  Hof, F., Kern, W., Kurz, S., Pashkovich, K., & Paulusma, D. (2020). Simple games versus weighted voting games: bounding the critical threshold value. Social Choice and Welfare, 54(4), 609-621. https://doi.org/10.1007/s00355-019-01221-6
• Clique-width and well-quasi ordering of triangle-free graph classes
  Dabrowski, K., Lozin, V., & Paulusma, D. (2020). Clique-width and well-quasi ordering of triangle-free graph classes. Journal of Computer and System Sciences, 108, 64-91. https://doi.org/10.1016/j.jcss.2019.09.001
• Connected vertex cover for (sP1+P5)-free graphs
  Johnson, M., Paesani, G., & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica, 82(1), 20-40. https://doi.org/10.1007/s00453-019-00601-9
• Clique-width for graph classes closed under complementation
  Blanché, A., Dabrowski, K., Johnson, M., Lozin, V., Paulusma, D., & Zamaraev, V. (2020). Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34(2), 1107-1147. https://doi.org/10.1137/18m1235016
• On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
  Dabrowski, K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D., & Rzążewski, P. (2020). On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. Algorithmica, 82(10), 2841-2866. https://doi.org/10.1007/s00453-020-00706-6
• Colouring Square-Free Graphs without Long Induced Paths
  Gaspers, S., Huang, S., & Paulusma, D. (2019). Colouring Square-Free Graphs without Long Induced Paths. Journal of Computer and System Sciences, 106, 60-79. https://doi.org/10.1016/j.jcss.2019.06.002
• Filling the complexity gaps for colouring planar and bounded degree graphs
  Dabrowski, K., Dross, F., Johnson, M., & Paulusma, D. (2019). Filling the complexity gaps for colouring planar and bounded degree graphs. Journal of Graph Theory, 92(4), 377-393. https://doi.org/10.1002/jgt.22459
• Using contracted solution graphs for solving reconfiguration problems
  Bonsma, P., & Paulusma, D. (2019). Using contracted solution graphs for solving reconfiguration problems. Acta Informatica, 56(7-8), 619-648. https://doi.org/10.1007/s00236-019-00336-8
• Bounding clique-width via perfect graphs
  Dabrowski, K., Huang, S., & Paulusma, D. (2019). Bounding clique-width via perfect graphs. Journal of Computer and System Sciences, 104, 202-215. https://doi.org/10.1016/j.jcss.2016.06.007
• Hereditary graph classes: when the complexities of coloring and clique cover coincide
  Blanché, A., Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory, 91(3), 267-289. https://doi.org/10.1002/jgt.22431
• Classifying k-Edge Colouring for H-free Graphs
  Galby, E., Lima, P., Paulusma, D., & Ries, B. (2019). Classifying k-Edge Colouring for H-free Graphs. Information Processing Letters, 146, 39-43. https://doi.org/10.1016/j.ipl.2019.02.006
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
  Golovach, P., Heggernes, P., Kratch, D., Lima, P., & Paulusma, D. (2019). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Algorithmica, 81(7), 2795-2828. https://doi.org/10.1007/s00453-019-00555-y
• On the parameterized complexity of (k,s)-SAT
  Paulusma, D., & Szeider, S. (2019). On the parameterized complexity of (k,s)-SAT. Information Processing Letters, 43, 34-36. https://doi.org/10.1016/j.ipl.2018.11.005
• Critical vertices and edges in H-free graphs
  Paulusma, D., Picouleau, C., & Ries, B. (2019). Critical vertices and edges in H-free graphs. Discrete Applied Mathematics, 257, 361-367. https://doi.org/10.1016/j.dam.2018.08.016
• Surjective H-colouring: New hardness results
  Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084
• Surjective H-Colouring over reflexive digraphs
  Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431
• Computing square roots of graphs with low maximum degree
  Cochefert, M., Couturier, J.-F., Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2018). Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics, 248, 93-101. https://doi.org/10.1016/j.dam.2017.04.041
• Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs
  Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2018). Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs. Theoretical Computer Science, 746, 49-72. https://doi.org/10.1016/j.tcs.2018.06.023
• Finding cactus roots in polynomial time
  Golovach, P., Kratsch, D., Stewart, A., & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems, 62(6), 1409-1426. https://doi.org/10.1007/s00224-017-9825-2
• Well-quasi-ordering versus clique-width: new results on bigenic classes
  Dabrowski, K., Lozin, V., & Paulusma, D. (2018). Well-quasi-ordering versus clique-width: new results on bigenic classes. Order, 35(2), 253-274. https://doi.org/10.1007/s11083-017-9430-7
• On colouring (2P2,H)-free and (P5,H)-free graphs
  Dabrowski, K., & Paulusma, D. (2018). On colouring (2P2,H)-free and (P5,H)-free graphs. Information Processing Letters, 134, 35-41. https://doi.org/10.1016/j.ipl.2018.02.003
• Independent Feedback Vertex Set for P5-free Graphs
  Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica, 81(4), 1416-1449. https://doi.org/10.1007/s00453-018-0474-x
• Independent feedback vertex sets for graphs of bounded diameter
  Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131, 26-32. https://doi.org/10.1016/j.ipl.2017.11.004
• The Stable Fixtures Problem with Payments
  Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2018). The Stable Fixtures Problem with Payments. Games and Economic Behavior, 108, 245-268. https://doi.org/10.1016/j.geb.2017.02.002
• Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity
  Chiarelli, N., Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2018). Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity. Theoretical Computer Science, 705, 75-83. https://doi.org/10.1016/j.tcs.2017.09.033
• Contracting Bipartite Graphs to Paths and Cycles
  Dabrowski, K., & Paulusma, D. (2017). Contracting Bipartite Graphs to Paths and Cycles. Information Processing Letters, 127, 37-42. https://doi.org/10.1016/j.ipl.2017.06.013
• Colouring Diamond-free Graphs
  Dabrowski, K., Dross, F., & Paulusma, D. (2017). Colouring Diamond-free Graphs. Journal of Computer and System Sciences, 89, 410-431. https://doi.org/10.1016/j.jcss.2017.06.005
• A linear kernel for finding square roots of almost planar graphs
  Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science, 689, 36-47. https://doi.org/10.1016/j.tcs.2017.05.008
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
  Golovach, P., Johnson, M., Paulusma, D., & Song., J. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory, 84(4), 331-363. https://doi.org/10.1002/jgt.22028
• Bounding the Clique-Width of H-free Chordal Graphs
  Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2017). Bounding the Clique-Width of H-free Chordal Graphs. Journal of Graph Theory, 86(1), 42-77. https://doi.org/10.1002/jgt.22111
• The price of connectivity for feedback vertex set
  Belmonte, R., van ’t Hof, P., Kamiński, M., & Paulusma, D. (2017). The price of connectivity for feedback vertex set. Discrete Applied Mathematics, 217(Part B), 132-143. https://doi.org/10.1016/j.dam.2016.08.011
• Graph editing to a fixed target
  Golovach, P., Paulusma, D., & Stewart, I. (2017). Graph editing to a fixed target. Discrete Applied Mathematics, 216(Part 1), 181-190. https://doi.org/10.1016/j.dam.2014.07.008
• Kempe equivalence of colourings of cubic graphs
  Feghali, C., Johnson, M., & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics, 59, 1-10. https://doi.org/10.1016/j.ejc.2016.06.008
• A Reconfigurations Analogue of Brooks' Theorem and Its Consequences
  Feghali, C., Johnson, M., & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4), 340-358. https://doi.org/10.1002/jgt.22000
• Editing to a Planar Graph of Given Degrees
  Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2016). Editing to a Planar Graph of Given Degrees. Journal of Computer and System Sciences, 85, 168-182. https://doi.org/10.1016/j.jcss.2016.11.009
• Minimal Disconnected Cuts in Planar Graphs
  Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks, 68(4), 250-259. https://doi.org/10.1002/net.21696
• The price of connectivity for cycle transversals
  Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2016). The price of connectivity for cycle transversals. European Journal of Combinatorics, 58, 203-224. https://doi.org/10.1016/j.ejc.2016.06.003
• Bounding the clique-width of H-free split graphs
  Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2016). Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics, 211, 30-39. https://doi.org/10.1016/j.dam.2016.04.003
• Model counting for CNF formulas of bounded modular treewidth
  Paulusma, D., Slivovsky, S., & Szeider, S. (2016). Model counting for CNF formulas of bounded modular treewidth. Algorithmica, 76(1), 168-194. https://doi.org/10.1007/s00453-015-0030-x
• Induced disjoint paths in circular-arc graphs in linear time
  Golovach, P., Paulusma, D., & van Leeuwen, E. (2016). Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science, 640, 70-83. https://doi.org/10.1016/j.tcs.2016.06.003
• Finding Shortest Paths Between Graph Colourings
  Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2), 295-321. https://doi.org/10.1007/s00453-015-0009-7
• Clique-width of graph classes defined by two forbidden induced subgraphs
  Dabrowski, K. K., & Paulusma, D. (2016). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 59(5), 650-666. https://doi.org/10.1093/comjnl/bxv096
• Editing to Eulerian graphs
  Dabrowski, K., Golovach, P., van 't Hof, P., & Paulusma, D. (2016). Editing to Eulerian graphs. Journal of Computer and System Sciences, 82(2), 213-228. https://doi.org/10.1016/j.jcss.2015.10.003
• Classifying the clique-width of H-free bipartite graphs
  Dabrowski, K., & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200, 43-51. https://doi.org/10.1016/j.dam.2015.06.030
• Parameterized algorithms for finding square roots
  Cochefert, M., Couturier, J.-. F., Golovach, P. A., & Paulusma, D. (2016). Parameterized algorithms for finding square roots. Algorithmica, 74(2), 602-629. https://doi.org/10.1007/s00453-014-9967-4
• Narrowing the complexity gap for colouring (Cs, Pt)-free graphs
  Huang, S., Johnson, M., & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal, 58(11), 3074-3088. https://doi.org/10.1093/comjnl/bxv039
• Knocking out P_k-free graphs
  Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010
• Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
  Broersma, H., Fiala, J., Golovach, P., Kaiser, T., Paulusma, D., & Proskurowski, A. (2015). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Journal of Graph Theory, 79(4), 282-299. https://doi.org/10.1002/jgt.21832
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
  Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesař, M. (2015). Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science, 590, 86-95. https://doi.org/10.1016/j.tcs.2015.01.028
• Modifying a Graph Using Vertex Elimination
  Golovach, P., Heggernes, P., Hof, V. '. P., Manne, F., Paulusma, D., & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica, 72(1), 99-125. https://doi.org/10.1007/s00453-013-9848-2
• Algorithms for diversity and clustering in social networks through dot product graphs
  Johnson, M., Paulusma, D., & van Leeuwen, E. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks, 41, 48-55. https://doi.org/10.1016/j.socnet.2015.01.001
• The computational complexity of disconnected cut and 2K2-partition
  Martin, B., & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B, 111, 17-37. https://doi.org/10.1016/j.jctb.2014.09.002
• Coloring graphs characterized by a forbidden subgraph
  Golovach, P., Paulusma, D., & Ries, B. (2015). Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics, 180, 101-110. https://doi.org/10.1016/j.dam.2014.08.008
• Induced disjoint paths in claw-free graphs
  Golovach, P., Paulusma, D., & van Leeuwen, E. (2015). Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics, 29(1), 348-375. https://doi.org/10.1137/140963200
• List Coloring in the Absence of a Linear Forest
  Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica, 71(1), 21-35. https://doi.org/10.1007/s00453-013-9777-0
• Closing complexity gaps for coloring problems on H-free graphs
  Golovach, P., Paulusma, D., & Song, J. (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation, 237, 204-214. https://doi.org/10.1016/j.ic.2014.02.004
• Parameterized complexity of three edge contraction problems with degree constraints
  Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2014). Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica, 51(7), 473-497. https://doi.org/10.1007/s00236-014-0204-z
• Detecting fixed patterns in chordal graphs in polynomial time
  Belmonte, R., Golovach, P., Heggernes, P., van 't Hof, P., Kaminski, M., & Paulusma, D. (2014). Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica, 69(3), 501-521. https://doi.org/10.1007/s00453-013-9748-5
• Solutions for the stable roommates problem with payments
  Biró, P., Bomhoff, M., Golovach, P., Kern, W., & Paulusma, D. (2014). Solutions for the stable roommates problem with payments. Theoretical Computer Science, 540-541, 53-61. https://doi.org/10.1016/j.tcs.2013.03.027
• Packing bipartite graphs with covers of complete bipartite graphs
  Chalopin, J., & Paulusma, D. (2014). Packing bipartite graphs with covers of complete bipartite graphs. Discrete Applied Mathematics, 168, 40-50. https://doi.org/10.1016/j.dam.2012.08.026
• Coloring graphs without short cycles and long induced paths
  Golovach, P., Paulusma, D., & Song, J. (2014). Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics, 167, 107-120. https://doi.org/10.1016/j.dam.2013.12.008
• List coloring in the absence of two subgraphs
  Golovach, P., & Paulusma, D. (2014). List coloring in the absence of two subgraphs. Discrete Applied Mathematics, 166, 123-130. https://doi.org/10.1016/j.dam.2013.10.010
• Obtaining Online Ecological Colourings by Generalizing First-Fit
  Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2014). Obtaining Online Ecological Colourings by Generalizing First-Fit. Theory of Computing Systems, 54(2), 244-260. https://doi.org/10.1007/s00224-013-9513-9
• Colouring of graphs with Ramsey-type forbidden subgraphs
  Dabrowski, K., Golovach, P., & Paulusma, D. (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science, 522, 34-43. https://doi.org/10.1016/j.tcs.2013.12.004
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
  Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27(1), 132-143. https://doi.org/10.1007/s10878-012-9490-y
• Lift-contractions
  Golovach, P., Paulusma, D., Kaminski, M., & Thilikos, D. (2014). Lift-contractions. European Journal of Combinatorics, 35, 286-296. https://doi.org/10.1016/j.ejc.2013.06.026
• Characterizing graphs of small carving-width
  Belmonte, R., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036
• Detecting induced minors in AT-free graphs
  Golovach, P., Kratsch, D., & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482, 20-32. https://doi.org/10.1016/j.tcs.2013.02.029
• Satisfiability of acyclic and almost acyclic CNF formulas
  Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99. https://doi.org/10.1016/j.tcs.2012.12.039
• Three complexity results on coloring Pk-free graphs
  Broersma, H., Fomin, F., Golovach, P., & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics, 34(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008
• Increasing the minimum degree of a graph by contractions
  Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481, 74-84. https://doi.org/10.1016/j.tcs.2013.02.030
• Obtaining planarity by contracting few edges
  Golovach, P., van 't Hof, P., & Paulusma, D. (2013). Obtaining planarity by contracting few edges. Theoretical Computer Science, 476, 38-46. https://doi.org/10.1016/j.tcs.2012.12.041
• Choosability on H-free graphs
  Golovach, P., Heggernes, P., van 't Hof, P., & Paulusma, D. (2013). Choosability on H-free graphs. Information Processing Letters, 113(4), 107-110. https://doi.org/10.1016/j.ipl.2012.12.003
• A note on contracting claw-free graphs
  Fiala, J., Kaminski, M., & Paulusma, D. (2013). A note on contracting claw-free graphs. Discrete Mathematics & Theoretical Computer Science, 15(2), 223-232
• 4-Coloring H-free graphs when H is small
  Golovach, P., Paulusma, D., & Song, J. (2013). 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics, 161(1-2), 140-150. https://doi.org/10.1016/j.dam.2012.08.022
• Exact algorithms for finding longest cycles in claw-free graphs
  Broersma, H., Fomin, F., Hof van 't, P., & Paulusma, D. (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica, 65(1), 129 -145. https://doi.org/10.1007/s00453-011-9576-4
• Detecting induced star-like minors in polynomial time
  Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002
• Computing vertex-surjective homomorphisms to partially reflexive trees
  Golovach, P., Paulusma, D., & Song, J. (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science, 457, 86-100. https://doi.org/10.1016/j.tcs.2012.06.039
• Finding vertex-surjective graph homomorphisms
  Golovach, P., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. Acta Informatica, 49(6), 381-394. https://doi.org/10.1007/s00236-012-0164-0
• On the parameterized complexity of coloring graphs in the absence of a linear forest
  Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2012). On the parameterized complexity of coloring graphs in the absence of a linear forest. Journal of discrete algorithms, 15, 56-62. https://doi.org/10.1016/j.jda.2012.04.008
• Computing role assignments of proper interval graphs in polynomial time
  Heggernes, P., van 't Hof, P., & Paulusma, D. (2012). Computing role assignments of proper interval graphs in polynomial time. Journal of discrete algorithms, 14, 173-188. https://doi.org/10.1016/j.jda.2011.12.004
• Distance three labelings of trees
  Fiala, J., Golovach, P., Kratochvil, J., Lidický, B., & Paulusma, D. (2012). Distance three labelings of trees. Discrete Applied Mathematics, 160(6), 764-779. https://doi.org/10.1016/j.dam.2011.02.004
• On graph contractions and induced minors
  Hof, P. V. '., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. (2012). On graph contractions and induced minors. Discrete Applied Mathematics, 160(6), 799-809. https://doi.org/10.1016/j.dam.2010.05.005
• Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
  Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. Theoretical Computer Science, 423, 1-10. https://doi.org/10.1016/j.tcs.2011.12.076
• Induced packing of odd cycles in planar graphs
  Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2012). Induced packing of odd cycles in planar graphs. Theoretical Computer Science, 420, 28-35. https://doi.org/10.1016/j.tcs.2011.11.004
• The k-in-a-path problem for claw-free graphs
  Fiala, J., Kamiński, M., Lidický, B., & Paulusma, D. (2012). The k-in-a-path problem for claw-free graphs. Algorithmica, 62(1-2), 499-519. https://doi.org/10.1007/s00453-010-9468-z
• Finding induced paths of given parity in claw-free graphs
  Hof van 't, P., Kamiński, M., & Paulusma, D. (2012). Finding induced paths of given parity in claw-free graphs. Algorithmica, 62(1-2), 537-563. https://doi.org/10.1007/s00453-010-9470-5
• Updating the complexity status of coloring graphs without a fixed induced linear forest
  Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoretical Computer Science, 414(1), 9-19. https://doi.org/10.1016/j.tcs.2011.10.005
• Computing solutions for matching games
  Biro, P., Kern, W., & Paulusma, D. (2012). Computing solutions for matching games. International Journal of Game Theory, 41(1), 75-90. https://doi.org/10.1007/s00182-011-0273-y
• Containment relations in split graphs
  Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Containment relations in split graphs. Discrete Applied Mathematics, 160(1-2), 155-163. https://doi.org/10.1016/j.dam.2011.10.004
• On partitioning a graph into two connected subgraphs
  Paulusma, D., & Rooij van, J. (2011). On partitioning a graph into two connected subgraphs. Theoretical Computer Science, 412(48), 6761-6769. https://doi.org/10.1016/j.tcs.2011.09.001
• Parameterizing cut sets in a graph by the number of their components
  Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). Parameterizing cut sets in a graph by the number of their components. Theoretical Computer Science, 412(45), 6340-6350. https://doi.org/10.1016/j.tcs.2011.07.005
• Graph labelings derived from models in distributed computing: a complete complexity classification
  Chalopin, J., & Paulusma, D. (2011). Graph labelings derived from models in distributed computing: a complete complexity classification. Networks, 58(3), 207-231. https://doi.org/10.1002/net.20432
• Contracting planar graphs to contractions of triangulations
  Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Contracting planar graphs to contractions of triangulations. Journal of discrete algorithms, 9(3), 299-306. https://doi.org/10.1016/j.jda.2011.03.010
• On disconnected cuts and separators
  Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). On disconnected cuts and separators. Discrete Applied Mathematics, 159(13), 1345-1351. https://doi.org/10.1016/j.dam.2011.04.027
• Computing role assignments of chordal graphs
  Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40-42), 3601-3613. https://doi.org/10.1016/j.tcs.2010.05.041
• Computing sharp 2-factors in claw-free graphs
  Broersma, H., & Paulusma, D. (2010). Computing sharp 2-factors in claw-free graphs. Journal of discrete algorithms, 8(3), 321-329. https://doi.org/10.1016/j.jda.2009.07.001
• Path factors and parallel knock-out schemes of almost claw-free graphs
  Johnson, M., Paulusma, D., & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Mathematics, 310(9), 1413-1423. https://doi.org/10.1016/j.disc.2009.04.022
• Comparing universal covers in polynomial time
  Fiala, J., & Paulusma., D. (2010). Comparing universal covers in polynomial time. Theory of Computing Systems, 46(4), 620-635. https://doi.org/10.1007/s00224-009-9200-z
• A new characterization of P6-free graphs
  Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025
• Partitioning graphs into connected parts
  Hof, P. V. '., Paulusma, D., & Woeginger, G. J. (2009). Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49), 4834-4843. https://doi.org/10.1016/j.tcs.2009.06.028
• Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs
  Broersma, H., Paulusma, D., & Yoshimoto, K. (2009). Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs. Graphs and Combinatorics, 25(4), 427-460. https://doi.org/10.1007/s00373-009-0855-7
• On the core and f-nucleolus of flow games
  Kern, W., & Paulusma, D. (2009). On the core and f-nucleolus of flow games. Mathematics of Operations Research, 34(4), 981-991. https://doi.org/10.1287/moor.1090.0405
• λ-backbone colorings along pairwise disjoint stars and matchings
  Broersma, H., Fujisawa, J., Marchal, L., Paulusma, D., Salman, A., & Yoshimoto, K. (2009). λ-backbone colorings along pairwise disjoint stars and matchings. Discrete Mathematics, 309(18), 5596-5609. https://doi.org/10.1016/j.disc.2008.04.007
• Covering graphs with few complete bipartite subgraphs
  Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2009). Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23), 2045-2053. https://doi.org/10.1016/j.tcs.2008.12.059
• Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number
  Broersma, H., Marchal, L., Paulusma, D., & Salman, A. (2009). Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. Discussiones Mathematicae. Graph Theory, 29(1), 143-162. https://doi.org/10.7151/dmgt.1437
• Upper bounds and algorithms for parallel knock-out numbers
  Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024
• The computational complexity of graph contractions II: two tough polynomially solvable cases
  Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks, 52(1), 32-56. https://doi.org/10.1002/net.20249
• Locally constrained graph homomorphisms and equitable partitions
  Fiala, J., Paulusma, D., & Telle, J. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics, 29(4), 850-880. https://doi.org/10.1016/j.ejc.2007.11.006
• The computational complexity of graph contractions I: polynomially solvable and NP-complete cases
  Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks, 51(3), 178-189. https://doi.org/10.1002/net.20214
• Relative length of longest paths and longest cycles in triangle-free graphs
  Paulusma, D., & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics, 308(7), 1222-1229. https://doi.org/10.1016/j.disc.2007.03.070
• The computational complexity of the parallel knock-out problem
  Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021
• A new algorithm for on-line coloring bipartite graphs
  Broersma, H., Capponi, A., & Paulusma, D. (2008). A new algorithm for on-line coloring bipartite graphs. SIAM Journal on Discrete Mathematics, 22(1), 72-91. https://doi.org/10.1137/060668675
• Cycles through specified vertices in triangle-free graphs
  Paulusma, D., & Yoshimito, K. (2007). Cycles through specified vertices in triangle-free graphs. Discussiones Mathematicae. Graph Theory, 27(1), 179-191. https://doi.org/10.7151/dmgt.1354
• A complete complexity classification of the role assignment problem
  Fiala, J., & Paulusma, D. (2005). A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1), 67-81. https://doi.org/10.1016/j.tcs.2005.09.029
• The computational complexity of the elimination problem in generalized sports competitions
  Kern, W., & Paulusma, D. (2004). The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1(2), 205-214. https://doi.org/10.1016/j.disopt.2003.12.003
• Matching games : the least core and the nucleolus
  Kern, W., & Paulusma, D. (2003). Matching games : the least core and the nucleolus. Mathematics of Operations Research, 28(2), 294-308. https://doi.org/10.1287/moor.28.2.294.14477
• Two extensions of the Shapley value for cooperative games
  Driessen, T., & Paulusma, D. (2001). Two extensions of the Shapley value for cooperative games. Mathematical Methods of Operations Research, 53(1), 35-49. https://doi.org/10.1007/s001860000099
• The new FIFA rules are hard: complexity aspects of sports competitions
  Kern, W., & Paulusma, D. (2001). The new FIFA rules are hard: complexity aspects of sports competitions. Discrete Applied Mathematics, 108(3), 317-323. https://doi.org/10.1016/s0166-218x%2800%2900241-9
• Note on the computational complexity of least core concepts for min-cost spanning tree games
  Faigle, U., Kern, W., & Paulusma, D. (2000). Note on the computational complexity of least core concepts for min-cost spanning tree games. Mathematical Methods of Operations Research, 52(1), 23-38. https://doi.org/10.1007/s001860000059

Report

• New Bounds for the Snake-in-the-Box Problem
  Allison, D., & Paulusma, D. (2019). New Bounds for the Snake-in-the-Box Problem. [No known commissioning body]
• On Finding Paths Passing through Specified Vertices
  Paulusma, D. (2011). On Finding Paths Passing through Specified Vertices. [No known commissioning body]