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 (pp. 1-10). Springer Nature Switzerland. 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. (2025). The Complexity of Diameter on H-free Graphs. In Graph-Theoretic Concepts in Computer Science (pp. 444-459). Springer. https://doi.org/10.1007/978-3-031-75409-8_31
• Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs,
  
  Lucke, F., Momeni, A., Paulusma, D., & Smith, S. (2025). Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs,. Lecture Notes in Computer Science, 415-429. https://doi.org/10.1007/978-3-031-75409-8_29
• 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). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024) (pp. 47:1-47:18). Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.ISAAC.2024.47
• Complexity framework for forbidden subgraphs IV: The Steiner Forest problem
  
  Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. .J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024). Complexity framework for forbidden subgraphs IV: The Steiner Forest problem. Lecture Notes in Computer Science, 14764, 206-217. https://doi.org/10.1007/978-3-031-63021-7_16
• 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). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) (pp. 29:1-29:17). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SWAT.2024.29
• 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). Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded. In Proceedings of AAMAS-2024 (pp. 2153-2155).
• Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
  
  Lucke, F., Paulusma, D., & Ries, B. (2023). Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (pp. 64:1-64:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.64
• 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). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (pp. 57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57
• Matching cuts in graphs of high girth and H-free graphs
  
  Feghali, C., Lucke, F., Paulusma, D., & Ries, B. (2023). Matching cuts in graphs of high girth and H-free graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023) (pp. 31:1-31:16). https://doi.org/10.4230/LIPIcs.ISAAC.2023.31
• Computing Subset Vertex Covers in H-Free Graphs
  
  Brettell, N., Oostveen, J. J., Pandey, S., Paulusma, D., & van Leeuwen, E. J. (2023). Computing Subset Vertex Covers in H-Free Graphs. In Fundamentals of Computation Theory 24th International Symposium, FCT 2023, Trier, Germany, September 18–21, 2023, Proceedings (pp. 88-102). Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-43587-4_7
• Computing Balanced Solutions for Large International Kidney Exchange Schemes
  
  Benedek, M., Biró, P., Kern, W., & Paulusma, D. (2022). Computing Balanced Solutions for Large International Kidney Exchange Schemes. In AAMAS ’22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (pp. 82-90). ACM. https://doi.org/10.5555/3535850.3535861
• Finding matching cuts in H-free graphs
  
  Lucke, F., Paulusma, D., & Ries, B. (2022). Finding matching cuts in H-free graphs. In S. W. Bae & H. Park (Eds.), 33rd International Symposium on Algorithms and Computation (ISAAC 2022) (pp. 22:1-22:16). Dagstuhl. https://doi.org/10.4230/lipics.isaac.2022.22
• Classifying Subset Feedback Vertex Set for H-free graphs
  
  Paesani, G., Paulusma, D., & Rzążewski, P. (2022). Classifying Subset Feedback Vertex Set for H-free graphs. In M. A. Bekos & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022. (pp. 412-424). Springer Verlag. https://doi.org/10.1007/978-3-031-15914-5_30
• Few induced disjoint paths for H-free graphs
  
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Few induced disjoint paths for H-free graphs. In I. Ljubić, F. Barahona, S. S. Dey, & A. Ridha Mahjoub (Eds.), Combinatorial Optimization 7th International Symposium, ISCO 2022 (pp. 89-101). Springer. https://doi.org/10.1007/978-3-031-18530-4_7
• Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
  
  Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (pp. 398-411). Springer Verlag. https://doi.org/10.1007/978-3-031-15914-5_29
• The Complexity of L(p,q)-Edge-Labelling
  
  Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (pp. 175-186). Springer Verlag. https://doi.org/10.1007/978-3-030-96731-4_15
• An algorithmic framework for locally constrained homomorphisms
  
  Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2022). An algorithmic framework for locally constrained homomorphisms. In M. A. Bekos & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022. (pp. 114-128). Springer Verlag. https://doi.org/10.1007/978-3-031-15914-5_9
• Injective colouring for H-free graphs
  
  Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free graphs. In Lecture Notes in Computer Science. Springer Verlag.
• Steiner trees for hereditary graph classes
  
  Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2021). Steiner trees for hereditary graph classes. In Y. Kohayakawa & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (pp. 613-624). Springer Verlag. https://doi.org/10.1007/978-3-030-61792-9_48
• Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs
  
  Paesani, G., Paulusma, D., & Rzążewski, P. (2021). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs. In F. Bonchi & S. J. Puglisi (Eds.), Leibniz International Proceedings in Informatics (pp. 1-14). Dagstuhl. https://doi.org/10.4230/lipics.mfcs.2021.82
• Acyclic, star and injective colouring: bounding the diameter
  
  Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Łukasz Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers (1st ed., pp. 336-348). Springer Verlag. https://doi.org/10.1007/978-3-030-86838-3_26
• Partitioning H-free graphs of bounded diameter
  
  Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021). Partitioning H-free graphs of bounded diameter. In H. Ahn & K. Sadakane (Eds.), Leibniz International Proceedings in Informatics (pp. 21:1-21:14). Schloss Dagstuhl. https://doi.org/10.4230/lipics.isaac.2021.21
• Colouring graphs of bounded diameter in the absence of small cycles
  
  Martin, B., Paulusma, D., & Smith, S. (2021). Colouring graphs of bounded diameter in the absence of small cycles. In T. Calamoneri & F. Corò (Eds.), Lecture Notes in Computer Science (pp. 367-380). Springer Verlag. https://doi.org/10.1007/978-3-030-75242-2_26
• Computing weighted subset transversals in H-free graphs
  
  Brettell, N., Johnson, M., & Paulusma, D. (2021). Computing weighted subset transversals in H-free graphs. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (pp. 229-242). Springer Verlag. https://doi.org/10.1007/978-3-030-83508-8_17
• QCSP on reflexive tournaments
  
  Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), Leibniz International Proceedings in Informatics (pp. 58:1-58:15). Dagstuhl. https://doi.org/10.4230/lipics.esa.2021.58
• Disjoint paths and connected subgraphs for H-free graphs
  
  Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2021). Disjoint paths and connected subgraphs for H-free graphs. In P. Flocchini & L. Moura (Eds.), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings (pp. 414-427). Springer Verlag. https://doi.org/10.1007/978-3-030-79987-8_29
• Solving problems on generalized convex graphs via mim-width
  
  Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. (2021). Solving problems on generalized convex graphs via mim-width. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (pp. 200-214). Springer Verlag. https://doi.org/10.1007/978-3-030-83508-8_15
• Computing subset transversals in H-free graphs
  
  Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020). Computing subset transversals in H-free graphs. In I. Adler & H. Müller (Eds.), WG 2020: Graph-Theoretic Concepts in Computer Science (pp. 187-199). Springer Verlag. https://doi.org/10.1007/978-3-030-60440-0_15
• Clique-Width: Harnessing the Power of Atoms
  
  Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2020). Clique-Width: Harnessing the Power of Atoms. In I. Adler & H. Müller (Eds.), Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers. (pp. 119-133). Springer Verlag. https://doi.org/10.1007/978-3-030-60440-0_10
• Bounding the mim-width of hereditary graph classes
  
  Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2020). Bounding the mim-width of hereditary graph classes. In Y. Cao & M. Pilipczuk (Eds.), 15th International Symposium on Parameterized and Exact Computation (pp. 187-199). Schloss Dagstuhl. https://doi.org/10.4230/lipics.ipec.2020.6
• Contracting to a longest path in H-free graphs
  
  Kern, W., & Paulusma, D. (2020). Contracting to a longest path in H-free graphs. In Y. Cao, S. Cheng, & M. Li (Eds.), 31st International Symposium on Algorithms and Computation (ISAAC 2020) (pp. 22:1-22:18). Schloss Dagstuhl. https://doi.org/10.4230/lipics.isaac.2020.22
• Acyclic, star and injective colouring: a complexity picture for H-free graphs
  
  Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020). Acyclic, star and injective colouring: a complexity picture for H-free graphs. In Leibniz International Proceedings in Informatics. Schloss Dagstuhl. https://doi.org/10.4230/lipics.esa.2020.22
• Colouring H-free graphs of bounded diameter
  
  Martin, B., Paulusma, D., & Smith, S. (2019). Colouring H-free graphs of bounded diameter. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). (pp. 14:1-14:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2019.14
• Tree pivot-minors and linear rank-width
  
  Dabrowski, K., Dross, F., Jeong, J., Kanté, M., Kwon, O., Oum, S., & Paulusma, D. (2019, July 29). 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, July 29). 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). On cycle transversals and their connected variants in the absence of a small linear forest. In L. A. Gąsieniec, J. Jansson, & C. Levcopoulos (Eds.), Fundamentals of computation theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings. (pp. 258-273). Springer Verlag. https://doi.org/10.1007/978-3-030-25027-0_18
• Generalized matching games for international kidney exchange
  
  Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (2019). Generalized matching games for international kidney exchange. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (pp. 413-421). Association for Computing Machinery (ACM).
• Finding a small number of colourful components
  
  Bulteau, L., Dabrowski, K., Fertin, G., Johnson, M., Paulusma, D., & Vialette, S. (2019). Finding a small number of colourful components. In 30th Annual Symposium on Combinatorial Pattern Matching. Schloss Dagstuhl.
• Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
  
  Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. In Z. Friggstad, J. Sack, & M. R. Salavatipour (Eds.), Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings. (pp. 181-195). Springer Verlag. https://doi.org/10.1007/978-3-030-24766-9_14
• Colouring (Pr+Ps)-free graphs
  
  Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2018). Colouring (Pr+Ps)-free graphs. In W. Hsu, D. Lee, & C. Liao (Eds.), 29th International Symposium on Algorithms and Computation (ISAAC 2018). (pp. 5:1-5:13). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.isaac.2018.5
• Connected Vertex Cover for (sP1+P5)-free graphs
  
  Johnson, M., Paesani, G., & Paulusma, D. (2018). Connected Vertex Cover for (sP1+P5)-free graphs. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings. (pp. 279-291). Springer Verlag. https://doi.org/10.1007/978-3-030-00256-5_23
• Computing small pivot-minors
  
  Dabrowski, K. K., Dross, F., Jeong, J., Kanté, M. M., Kwon, O., Oum, S., & Paulusma, D. (2018). Computing small pivot-minors. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018 ; proceedings. (pp. 125-138). Springer Verlag. https://doi.org/10.1007/978-3-030-00256-5_11
• Simple games versus weighted voting games
  
  Hof, F., Kern, W., Kurz, S., & Paulusma, D. (2018). Simple games versus weighted voting games. In X. Deng (Ed.), Algorithmic game theory : 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings. (pp. 69-81). Springer Verlag. https://doi.org/10.1007/978-3-319-99660-8_7
• Colouring Square-Free Graphs without Long Induced Paths
  
  Gaspers, S., Huang, S., & Paulusma, D. (2018). Colouring Square-Free Graphs without Long Induced Paths. In R. Niedermeier & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France. (pp. 35:1-35:15). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.stacs.2018.35
• Surjective H-Colouring over Reflexive Digraphs
  
  Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over Reflexive Digraphs. In R. Niedermeier & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France. (pp. 49:1-49:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.stacs.2018.49
• 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). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). (pp. 63:1-63:15). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2018.63
• Disconnected Cuts in Claw-free Graphs
  
  Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018). Disconnected Cuts in Claw-free Graphs. In Y. Azar, H. Bast, & G. Herman (Eds.), 26th Annual European Symposium on Algorithms (ESA 2018). (pp. 61:1-61:14). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing. https://doi.org/10.4230/lipics.esa.2018.61
• Clique-Width for Graph Classes Closed under Complementation
  
  Blanché A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017). Clique-Width for Graph Classes Closed under Complementation. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2017.73
• Recognizing Graphs Close to Bipartite Graphs
  
  Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Recognizing Graphs Close to Bipartite Graphs. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2017.70
• Clique-width and well-quasi ordering of triangle-free graph classes
  
  Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017). Clique-width and well-quasi ordering of triangle-free graph classes. In H. L. Bodlaender & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers. (pp. 220-233). Springer Verlag. https://doi.org/10.1007/978-3-319-68705-6_17
• Reducing the chromatic number by vertex or edge deletions
  
  Picouleau, C., Paulusma, D., & Ries, B. (2017). Reducing the chromatic number by vertex or edge deletions. Electronic Notes in Discrete Mathematics, 62, 243-248. https://doi.org/10.1016/j.endm.2017.10.042
• Contracting bipartite graphs to paths and cycles
  
  Dabrowski, K., & Paulusma, D. (2017). Contracting bipartite graphs to paths and cycles. Electronic Notes in Discrete Mathematics, 61, 309-315. https://doi.org/10.1016/j.endm.2017.06.053
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
  
  Golovach, P., Heggernes, P., Kratsch, D., Lima, P., & Paulusma, D. (2017). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. In H. L. Bodlaender & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers. (pp. 275-288). Springer Verlag. https://doi.org/10.1007/978-3-319-68705-6_21
• Surjective H-Colouring: new hardness results
  
  Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017). Surjective H-Colouring: new hardness results. In J. Kari, F. Manea, & I. Petre (Eds.), Unveiling dynamics an complexity. (pp. 270-281). Springer Verlag. https://doi.org/10.1007/978-3-319-58741-7_26
• Blocking independent sets for H-free graphs via edge contractions and vertex deletions
  
  Paulusma, D., Picouleau, C., & Ries, B. (2017). Blocking independent sets for H-free graphs via edge contractions and vertex deletions. In T. Gopal, G. Jäger, & S. Steila (Eds.), Theory and Applications of Models of Computation, 14th Annual Conference (TAMC 2017) : Bern, Switzerland, April 20-22, 2017 ; proceedings. (pp. 470-483). Springer Verlag. https://doi.org/10.1007/978-3-319-55911-7_34
• Independent Feedback Vertex Set for P5-free Graphs
  
  Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Independent Feedback Vertex Set for P5-free Graphs. In Y. Okamoto & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation (ISAAC 2017) ; proceedings. (pp. 16:1-16:12). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/lipics.isaac.2017.16
• Squares of low clique number
  
  Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016). Squares of low clique number. Electronic Notes in Discrete Mathematics, 55, 195-198. https://doi.org/10.1016/j.endm.2016.10.048
• Reducing the clique and chromatic number via edge contractions and vertex deletions
  
  Paulusma, D., Picouleau, C., & Ries, B. (2016). Reducing the clique and chromatic number via edge contractions and vertex deletions. In R. Cerulli, S. Fujishige, & A. R. Mahjoub (Eds.), Combinatorial optimization : 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016. Revised selected papers. (pp. 38-49). Springer Verlag. https://doi.org/10.1007/978-3-319-45587-7_4
• Well-quasi-ordering versus clique-width: new results on bigenic classes
  
  Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016). Well-quasi-ordering versus clique-width: new results on bigenic classes. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings. (pp. 253-265). Springer Verlag. https://doi.org/10.1007/978-3-319-44543-4_20
• Finding cactus roots in polynomial time
  
  Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016). Finding cactus roots in polynomial time. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings. (pp. 361-372). Springer Verlag. https://doi.org/10.1007/978-3-319-44543-4_28
• The stable fixtures problem with payments
  
  Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2016). The stable fixtures problem with payments. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers. (pp. 49-63). Springer Verlag. https://doi.org/10.1007/978-3-662-53174-7_4
• Open problems on graph coloring for special graph classes
  
  Paulusma, D. (2016). Open problems on graph coloring for special graph classes. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers. (pp. 16-30). Springer Verlag. https://doi.org/10.1007/978-3-662-53174-7_2
• Using contracted solution graphs for solving reconfiguration problems
  
  Bonsma, P., & Paulusma, D. (2016). Using contracted solution graphs for solving reconfiguration problems. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22–26, 2016, Kraków, Poland.. Schloss Dagstuhl, Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.mfcs.2016.20
• Colouring diamond-free graphs
  
  Dabrowski, K. K., Dross, F., & Paulusma, D. (2016). Colouring diamond-free graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016).. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/lipics.swat.2016.16
• A linear kernel for finding square roots of almost planar graphs
  
  Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016). A linear kernel for finding square roots of almost planar graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016).. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/lipics.swat.2016.4
• Filling the complexity gaps for colouring planar and bounded degree graphs
  
  Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2016). Filling the complexity gaps for colouring planar and bounded degree graphs. In Z. Lipták & W. F. Smyth (Eds.), Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers. (pp. 100-111). Springer Verlag. https://doi.org/10.1007/978-3-319-29516-9_9
• What graphs are 2-dot product graphs?
  
  Johnson, M., van Leeuwen, E., & Paulusma, D. (2015). What graphs are 2-dot product graphs?. In Electronic Notes in Discrete Mathematics (pp. 705-711). Elsevier. https://doi.org/10.1016/j.endm.2015.06.095
• Kempe equivalence of colourings of cubic graphs
  
  Feghali, C., Johnson, M., & Paulusma, D. (2015). Kempe equivalence of colourings of cubic graphs. In Electronic Notes in Discrete Mathematics (pp. 243-249). Elsevier. https://doi.org/10.1016/j.endm.2015.06.034
• Bounding the clique-width of H-free split graphs
  
  Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015). Bounding the clique-width of H-free split graphs. In Electronic Notes in Discrete Mathematics (pp. 497-503). Elsevier. https://doi.org/10.1016/j.endm.2015.06.069
• The price of connectivity for cycle transversals
  
  Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2015). The price of connectivity for cycle transversals. In Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II. (pp. 395-406). Springer Verlag. https://doi.org/10.1007/978-3-662-48054-0_33
• Bounding the Clique-Width of H-free Chordal Graphs
  
  Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015). Bounding the Clique-Width of H-free Chordal Graphs. In Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II. (pp. 139-150). Springer Verlag. https://doi.org/10.1007/978-3-662-48054-0_12
• Minimal disconnected cuts in planar graphs
  
  Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. M. (2015). Minimal disconnected cuts in planar graphs. In A. Kosowski & I. Walukiewicz (Eds.), Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, proceedings. (pp. 243-254). Springer Verlag. https://doi.org/10.1007/978-3-319-22177-9_19
• Editing to a planar graph of given degrees
  
  Dabrowski, K., Golovach, P., van ’t Hof, P., Paulusma, D., & Thilikos, D. (2015). Editing to a planar graph of given degrees. In Computer science - theory and applications : 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, proceedings. (pp. 143-156). Springer Verlag. https://doi.org/10.1007/978-3-319-20297-6_10
• Clique-width of graph classes defined by two forbidden induced subgraphs
  
  Dabrowski, K. K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. In V. T. Paschos & P. Widmayer (Eds.), Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings. (pp. 167-181). Springer Verlag. https://doi.org/10.1007/978-3-319-18173-8_12
• Contraction blockers for graphs with forbidden induced paths
  
  Diner, Ö, Paulusma, D., Picouleau, C., & Ries, B. (2015). Contraction blockers for graphs with forbidden induced paths. In V. T. Paschos & P. Widmayer (Eds.), Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings. (pp. 194-207). Springer Verlag. https://doi.org/10.1007/978-3-319-18173-8_14
• Bounding clique-width via perfect graphs
  
  Dabrowski, K. K., Huang, S., & Paulusma, D. (2015). Bounding clique-width via perfect graphs. In A. Dediu, E. Formenti, C. Martín-Vide, & B. Truthe (Eds.), Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015 ; proceedings. (pp. 676-688). Springer Verlag. https://doi.org/10.1007/978-3-319-15579-1_53
• Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
  
  Belmonte, R., Hof, van ’t P., Kaminski, M., & Paulusma, D. (2014). Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29 August 2014 ; proceedings, Part II. (pp. 57-68). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_6
• Classifying the Clique-Width of H-Free Bipartite Graphs
  
  Dabrowski, K. K., & Paulusma, D. (2014). Classifying the Clique-Width of H-Free Bipartite Graphs. In Z. Cai, A. Zelikovsky, & A. G. Bourgeois (Eds.), 20th International Conference, COCOON 2014, Atlanta, GA, USA, 4-6 August 2014 ; proceedings. (pp. 489-500). Springer Verlag. https://doi.org/10.1007/978-3-319-08783-2_42
• Knocking Out P_k-free Graphs
  
  Johnson, M., Paulusma, D., & Stewart, A. (2014). Knocking Out P_k-free Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29August 2014 ; proceedings, Part II. (pp. 396-407). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_34
• Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs
  
  Huang, S., Johnson, M., & Paulusma, D. (2014). Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs. In Q. Gu, P. Hell, & B. Yang (Eds.), 10th International Conference, AAIM 2014, Vancouver, BC, Canada, 8-11 July 2014 ; proceedings. (pp. 162-173). Springer Verlag. https://doi.org/10.1007/978-3-319-07956-1_15
• Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
  
  Golovach, P., Paulusma, D., & van Leeuwen, E. (2014). Induced Disjoint Paths in Circular-Arc Graphs in Linear Time. In 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, 25-27 June 2014 ; revised selected papers. (pp. 225-237). Springer Verlag. https://doi.org/10.1007/978-3-319-12340-0_19
• A Reconfigurations Analogue of Brooks’ Theorem
  
  Feghali, C., Johnson, M., & Paulusma, D. (2014). A Reconfigurations Analogue of Brooks’ Theorem. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29 August 2014 ; proceedings, Part II. (pp. 287-298). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_25
• Finding Shortest Paths Between Graph Colourings
  
  Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2014). Finding Shortest Paths Between Graph Colourings. In M. Cygan & P. Heggernes (Eds.), 9th International Symposium, IPEC 2014, Wroclaw, Poland, 10-12 September 2014 ; revised selected papers. (pp. 221-233). Springer Verlag. https://doi.org/10.1007/978-3-319-13524-3_19
• Editing to Eulerian Graphs
  
  Dabrowski, K. K., Golovach, P. A., Hof, van’t P., & Paulusma, D. (2014). Editing to Eulerian Graphs. In V. Raman & S. P. Suresh (Eds.), 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). (pp. 97-108). Schloss Dagstuhl. https://doi.org/10.4230/lipics.fsttcs.2014.97
• Sparse Square Roots
  
  Cochefert, M., Couturier, J., Golovach, P. A., Kratsch, D., & Paulusma, D. (2013). Sparse Square Roots. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, Lübeck, Germany, 19-21 June 2013 ; revised papers. (pp. 177-188). Springer Verlag. https://doi.org/10.1007/978-3-642-45043-3_16
• Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
  
  Dabrowski, K. K., Golovach, P. A., & Paulusma, D. (2013). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers. (pp. 201-212). Springer Verlag. https://doi.org/10.1007/978-3-642-45043-3_18
• Model counting for CNF formuals of bounded module treewidth
  
  Paulusma, D., Slivovksy, F., & Szeider, S. (2013). Model counting for CNF formuals of bounded module treewidth. In N. Portier & T. Wilke (Eds.), 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). (pp. 55-66). Schloss Dagstuh. https://doi.org/10.4230/lipics.stacs.2013.55
• Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs
  
  Johnson, M., Paulusma, D., & van Leeuwen, E. (2013). Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. In L. Cai, S. Cheng, & T. Lam (Eds.), Algorithms and computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, 16-18 December 2013 ; proceedings. (pp. 130-140). Springer Verlag. https://doi.org/10.1007/978-3-642-45030-3_13
• The price of connectivity for feedback vertex set
  
  Belmonte, R., Hof, van ’t P., Kaminski, M., & Paulusma, D. (2013). The price of connectivity for feedback vertex set. In J. Nešetřil & M. Pellegrini (Eds.), The seventh European conference on combinatorics, graph theory and applications. (pp. 123-128). Scuola Normale Superiore. https://doi.org/10.1007/978-88-7642-475-5_20
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
  
  Belmonte, R., Golovach, P., Hof, van ’t P., & Paulusma, D. (2013). Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. In 8th International Symposium, IPEC 2013, 4-6 September 2013, Sophia Antipolis, France ; revised selected papers. (pp. 16-27). Springer Verlag. https://doi.org/10.1007/978-3-319-03898-8_3
• Graph editing to a fixed target
  
  Golovach, P., Paulusma, D., & Stewart, I. A. (2013). Graph editing to a fixed target. In T. Lecroq & L. Mouchard (Eds.), Combinatorial algorithms : 24th International Workshop, IWOCA 2013, 10-12 July 2013, Rouen, France ; revised selected papers. (pp. 192-205). Springer Verlag. https://doi.org/10.1007/978-3-642-45278-9_17
• Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
  
  Chaplick, S., Fiala, J., Hof, van ’t P., Paulusma, D., & Tesar, M. (2013). Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree. In L. Gąsieniec & F. Wolter (Eds.), Fundamentals of computation theory : 19th International Symposium, FCT 2013, 19-21 August 2013, Liverpool, UK ; proceedings. (pp. 121-132). Springer Verlag. https://doi.org/10.1007/978-3-642-40164-0_14
• List Coloring in the Absence of Two Subgraphs
  
  Golovach, P. A., & Paulusma, D. (2013). List Coloring in the Absence of Two Subgraphs. In P. G. Spirakis & M. Serna (Eds.), Algorithms and complexity : 8th International Conference, CIAC 2013, 22-24 May 2013, Barcelona, Spain ; proceedings. (pp. 288-299). Springer Verlag. https://doi.org/10.1007/978-3-642-38233-8_24
• 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). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers. (pp. 127-138). Springer Verlag. https://doi.org/10.1007/978-3-642-45043-3_12
• Solutions for the stable rommates problem with payments
  
  Biró, P., Bomhoff, M., Golovach, P. A., Kern, W., & Paulusma, D. (2012). Solutions for the stable rommates problem with payments. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers. (pp. 69-80). Springer Verlag. https://doi.org/10.1007/978-3-642-34611-8_10
• How to eliminate a graph
  
  Golovach, P., Heggernes, P., van ’t Hof, P., Manne, F., Paulusma, D., & Pilipczuk, M. (2012). How to eliminate a graph. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science: 38th international workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, revised selected papers. (pp. 320-331). Springer Verlag. https://doi.org/10.1007/978-3-642-34611-8_32
• Obtaining planarity by contracting few edges
  
  Golovach, P. A., van ’t Hog, P., & Paulusma, D. (2012). Obtaining planarity by contracting few edges. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th international symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings. (pp. 455-466). Springer Verlag. https://doi.org/10.1007/978-3-642-32589-2_41
• Characterizing graphs of small carving-width
  
  Belmonte, R., van ’t Hof, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Characterizing graphs of small carving-width. In G. Lin (Ed.), Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings. (pp. 360-370). Springer Verlag. https://doi.org/10.1007/978-3-642-31770-5_32
• Coloring graphs characterized by a forbidden subgraph
  
  Golovach, P. A., Paulusma, D., & Ries, B. (2012). Coloring graphs characterized by a forbidden subgraph. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings. (pp. 443-454). Springer Verlag. https://doi.org/10.1007/978-3-642-32589-2_40
• Detecting induced minors in AT-free graphs
  
  Golovach, P. A., Kratsch, D., & Paulusma, D. (2012). Detecting induced minors in AT-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings. (pp. 495-505). Springer Verlag. https://doi.org/10.1007/978-3-642-35261-4_52
• Closing complexity gaps for coloring problems on H-free graphs
  
  Golovach, P. A., Paulusma, D., & Song, J. (2012). Closing complexity gaps for coloring problems on H-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings. (pp. 14-23). Springer Verlag. https://doi.org/10.1007/978-3-642-35261-4_5
• Finding vertex-surjective graph homomorphisms
  
  Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. In E. A. Hirsch, J. Karhumäki, A. Lepistö, & M. Prilutskii (Eds.), Computer science : theory and applications : 7th International Computer Science Symposium in Russia, CSR 2012, 3-7 July 2012, Nizhny Novgorod, Russia ; proceedings. (pp. 160-171). Springer Verlag. https://doi.org/10.1007/978-3-642-30642-6_16
• 4-Coloring H-free graphs when H is small
  
  Golovach, P., Paulusma, D., & Song, J. (2012). 4-Coloring H-free graphs when H is small. In M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, & G. Turán (Eds.), Theory and practice of computer science : 38th Conference on Current trends in theory and practice of computer science, SOFSEM 2012, Špindlerův Mlýn, Czech Republic, 21-27 January 2012 ; proceedings. (pp. 289-300). Springer Verlag. https://doi.org/10.1007/978-3-642-27660-6_24
• Induced disjoint paths in claw-free graphs
  
  Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012). Induced disjoint paths in claw-free graphs. In L. Epstein & P. Ferragina (Eds.), Algorithms, 20th Annual European Symposium, ESA 2012, Ljubljana, Slovenia, 10-12 September 2012 ; proceedings. (pp. 515-526). Springer Verlag. https://doi.org/10.1007/978-3-642-33090-2_45
• Induced disjoint paths in AT-free graphs
  
  Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012). Induced disjoint paths in AT-free graphs. In F. V. Fomin & P. Kaski (Eds.), Algorithm Theory : 13th Scandinavian Symposium and Workshops, SWAT 2012, Helsinki, Finland, 4-6 July 2012 ; proceedings. (pp. 153-164). Springer Verlag. https://doi.org/10.1007/978-3-642-31155-0_14
• Lift Contractions
  
  Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Lift Contractions. Electronic Notes in Discrete Mathematics, 38(1), 407-412. https://doi.org/10.1016/j.endm.2011.09.066
• On the diameter of reconfiguration graphs for vertex colourings
  
  Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2011). On the diameter of reconfiguration graphs for vertex colourings. Electronic Notes in Discrete Mathematics, 38(1), 161-166. https://doi.org/10.1016/j.endm.2011.09.028
• Computing vertex-surjective homomorphisms to partially reflexive trees
  
  Golovach, P. A., Paulusma, D., & Song, J. (2011). Computing vertex-surjective homomorphisms to partially reflexive trees. In A. Kulikov & N. Vereshchagin (Eds.), Computer Science : Theory and Applications, 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011 ; proceedings. (pp. 261-274). Springer Verlag. https://doi.org/10.1007/978-3-642-20712-9_20
• List coloring in the absence of a linear forest
  
  Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011). List coloring in the absence of a linear forest. In P. Kolman & J. Kratochvil (Eds.), Graph-theoretic concepts in computer science, 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 ; revised papers. (pp. 119-130). Springer Verlag. https://doi.org/10.1007/978-3-642-25870-1_12
• Coloring graphs without short cycles and long induced paths
  
  Golovach, P. A., Paulusma, D., & Song, J. (2011). Coloring graphs without short cycles and long induced paths. In O. Owe, M. Steffen, & J. A. Telle (Eds.), Fundamentals of computation theory, 18th International Symposium (FCT 2011), 22-25 August 2011, Oslo, Norway ; proceedings. (pp. 193-204). Springer Verlag. https://doi.org/10.1007/978-3-642-22953-4_17
• Increasing the Minimum Degree of a Graph by Contractions
  
  Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). Increasing the Minimum Degree of a Graph by Contractions. In Parameterized and Exact Computation (pp. 67-79). https://doi.org/10.1007/978-3-642-28050-4_6
• Contracting a chordal graph to a split graph or a tree
  
  Golovach, P. A., Kaminski, M., & Paulusma, D. (2011). Contracting a chordal graph to a split graph or a tree. In F. Murlak & P. Sankowski (Eds.), Mathematical Foundations of Computer Science 2011, 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011 ; proceedings. (pp. 339-350). Springer Verlag. https://doi.org/10.1007/978-3-642-22993-0_32
• Satisfiability of acyclic and almost acyclic CNF formulas (II)
  
  Ordyniak, S., Paulusma, D., & Szeider, S. (2011). Satisfiability of acyclic and almost acyclic CNF formulas (II). In K. A. Sakallah & L. Simons (Eds.), Theory and Applications of Satisfiability Testing - SAT 2011, 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011 ; proceedings. (pp. 47-60). Springer Verlag. https://doi.org/10.1007/978-3-642-21581-0_6
• Computing Role Assignments of Proper Interval Graphs in Polynomial Time
  
  Heggernes, P., Hof, van’t P., & Paulusma, D. (2011). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. In C. S. Iliopoulos & W. F. Smyth (Eds.), Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, July 26-28, 2010, revised selected papers (pp. 167-180). Springer Verlag. https://doi.org/10.1007/978-3-642-19222-7_18
• The computational complexity of Disconnected Cut and 2K2-Partition
  
  Martin, B., & Paulusma, D. (2011). The computational complexity of Disconnected Cut and 2K2-Partition. In J. Lee (Ed.), Principles and practice of constraint programming, 17th International Conference, CP 2011, 12-16 September 2011, Perugia, Italy ; proceedings. (pp. 561-575). Springer Verlag. https://doi.org/10.1007/978-3-642-23786-7_43
• 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). Finding contractions and induced minors in chordal graphs via disjoint paths. In T. Asano, S. Nakano, Y. Okamoto, & O. Watanabe (Eds.), Algorithms and Computation, 22nd International Symposium, ISAAC 2011, Yokohama, Japan, 5-8 December 2011 ; proceedings. (pp. 110-119). Springer Verlag. https://doi.org/10.1007/978-3-642-25591-5_13
• Satisfiability of Acyclic and Almost Acyclic CNF Formulas
  
  Ordyniak, S., Paulusma, D., & Szeider, S. (2010). Satisfiability of Acyclic and Almost Acyclic CNF Formulas. In Leibniz International Proceedings in Informatics (LIPIcs) (pp. 84-95). https://doi.org/10.4230/lipics.fsttcs.2010.84
• Obtaining online ecological colourings by generalizing first-fit
  
  Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010). Obtaining online ecological colourings by generalizing first-fit. In F. Ablayev & E. W. Mayr (Eds.), Computer science : theory and applications : 5th International Computer Science Symposium in Russia, CSR, 16-20 June 2010, Kazan, Russia ; proceedings. (pp. 240-251). Springer Verlag. https://doi.org/10.1007/978-3-642-13182-0_22
• Packing bipartite graphs with covers of complete bipartite graphs
  
  Chalopin, J., & Paulusma, D. (2010). Packing bipartite graphs with covers of complete bipartite graphs. In T. Calamoneri & J. Diaz (Eds.), Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings. (pp. 276-287). Springer Verlag. https://doi.org/10.1007/978-3-642-13073-1_25
• L(2,1,1)-labeling is NP-complete for trees
  
  Golovach, P. A., Lidicky, B., & Paulusma, D. (2010). L(2,1,1)-labeling is NP-complete for trees. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings. (pp. 211-221). Springer Verlag. https://doi.org/10.1007/978-3-642-13562-0_20
• Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs
  
  Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010). Narrowing Down the Gap on the Complexity of Coloring Pk-Free Graphs. In Graph Theoretic Concepts in Computer Science (pp. 63-74). https://doi.org/10.1007/978-3-642-16926-7_8
• On contracting graphs to fixed pattern graphs
  
  ’t, H. P. van, Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010). On contracting graphs to fixed pattern graphs. In J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, & B. Rumpe (Eds.), Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, Špindleruv Mlýn, Czech Republic, 23-29 January 2010 ; proceedings. (pp. 503-514). Springer Verlag. https://doi.org/10.1007/978-3-642-11266-9_42
• On Coloring Graphs without Induced Forests
  
  Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2010). On Coloring Graphs without Induced Forests. In Algorithms and Computation (pp. 156-167). https://doi.org/10.1007/978-3-642-17514-5_14
• On solution concepts for matching games
  
  Biro, P., Kern, W., & Paulusma, D. (2010). On solution concepts for matching games. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings. (pp. 211-221). Springer Verlag. https://doi.org/10.1007/978-3-642-13562-0_12
• Contractions of planar graphs in polynomial time
  
  Kaminski, M., Paulusma, D., & Thilikos, D. (2010). Contractions of planar graphs in polynomial time. In Algorithms : ESA 2010 : 18th Annual European Symposium, 6-8 September 2010, Liverpool UK ; proceedings part I. (pp. 122-133). Springer Verlag. https://doi.org/10.1007/978-3-642-15775-2_11
• The k-in-a-path problem for claw-free graphs
  
  Fiala, J., Kaminski, M., Lidicky, B., & Paulusma, D. (2010). The k-in-a-path problem for claw-free graphs. In J. Marion & T. Schwentick (Eds.), 27th International symposium on theoretical aspects of computer science, STACS 2010, 4-6 March 2010 ; proceedings. (pp. 371-382). Dagstuhl. https://doi.org/10.4230/lipics.stacs.2010.2469
• 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. In M. Miller & K. Wada (Eds.), Proceedings of the International Workshop on Combinatorial Algorithms 2008. (pp. 27-41). College Publications.
• Parameterizing cut sets in a graph by the number of their components
  
  Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009). Parameterizing cut sets in a graph by the number of their components. In Y. Dong, D. Du, & I. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings. (pp. 605-615). Springer Verlag. https://doi.org/10.1007/978-3-642-10631-6_62
• Induced packing of odd cycles in a planar graph
  
  Golovach, P. A., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009). Induced packing of odd cycles in a planar graph. In Y. Dong, D. Du, & O. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings. (pp. 514-523). Springer Verlag. https://doi.org/10.1007/978-3-642-10631-6_53
• On partitioning a graph into two connected subgraphs
  
  Paulusma, D., & Rooij van, J. M. M. (2009). On partitioning a graph into two connected subgraphs. In Y. Dong, D. Du, & I. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings. (pp. 1215-1224). Springer Verlag. https://doi.org/10.1007/978-3-642-10631-6_122
• Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs
  
  Broersma, H. J., Fomin, F. V., Hof van ’t, P., & Paulusma, D. (2009). Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. In M. Habib & C. Paul (Eds.), Graph-theoretic concepts in computer science : 35th International Workshop, WG 2009, 24-26 June 2009, Montpellier, France ; revised papers. (pp. 44-53). Springer Verlag. https://doi.org/10.1007/978-3-642-11409-0_4
• Finding Induced Paths of Given Parity in Claw-Free Graphs
  
  Hof van ’t, P., Kaminski, M., & Paulusma, D. (2009). Finding Induced Paths of Given Parity in Claw-Free Graphs. In C. Paul & M. Habib (Eds.), Graph-theoretic concepts in computer science. (pp. 341-352). Springer Verlag. https://doi.org/10.1007/978-3-642-11409-0_30
• Three complexity results on coloring Pk-free graphs
  
  Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2009). Three complexity results on coloring Pk-free graphs. In J. Fiala, J. Kratochvíl, & M. Miller (Eds.), Combinatorial algorithms : 20th InternationalWorkshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers. (pp. 95-104). Springer Verlag. https://doi.org/10.1007/978-3-642-10217-2_12
• Computing role assignments of chordal graphs
  
  Hof, P. van ’t, Paulusma, D., & Rooij, J. van. (2009). Computing role assignments of chordal graphs. In Fundamentals of computation theory : 17th International Symposium, FCT 2009, Wrocław, Poland, September 2-4, 2009. Proceedings. (pp. 193-204). Springer Verlag. https://doi.org/10.1007/978-3-642-03409-1_18
• Partitioning graphs into connected parts
  
  Hof, P. van ’t, Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. In Computer science - theory and applications. (pp. 143-154). Springer Verlag. https://doi.org/10.1007/978-3-642-03351-3_15
• A new characterization of P6-free graphs
  
  Hof, P. van’t, & Paulusma, D. (2008). A new characterization of P6-free graphs. In X. Hu & J. Wang (Eds.), Computing and combinatorics, 14th Annual International Conference, COCOON 2008, 27-29 June 2008 Dalian, China ; proceedings. (pp. 415-424). Springer Verlag. https://doi.org/10.1007/978-3-540-69733-6_41
• Comparing universal covers in polynomial time
  
  Fiala, J., & Paulusma, D. (2008). Comparing universal covers in polynomial time. In E. A. Hirsch, A. A. Razboro, A. Semenov, & A. Slissenko (Eds.), Computer science – theory and applications, Third International Computer Science Symposium in Russia, CSR 2008, 7-12 June 2008, Moscow, Russia ; proceedings. (pp. 158-167). Springer Verlag. https://doi.org/10.1007/978-3-540-79709-8_18
• Computing sharp 2-factors in claw-free graphs
  
  Broersma, H. J., & Paulusma, D. (2008). Computing sharp 2-factors in claw-free graphs. In E. Ochmanski & J. Tyszkiewicz (Eds.), Mathematical foundations of computer science 2008, 33rd International Symposium, MFCS 2008, 25-29 August 2008, Toru´n, Poland ; proceedings. (pp. 193-204). Springer Verlag. https://doi.org/10.1007/978-3-540-85238-4_15
• On components of 2-factors in claw-free graphs
  
  Broersma, H., Paulusma, D., & Yoshimoto, K. (2007). On components of 2-factors in claw-free graphs. Electronic Notes in Discrete Mathematics, 29, 289-293. https://doi.org/10.1016/j.endm.2007.07.050
• Covering Graphs with Few Complete Bipartite Subgraphs
  
  Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2007). Covering Graphs with Few Complete Bipartite Subgraphs. In FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (pp. 340-351). https://doi.org/10.1007/978-3-540-77050-3_28
• Upper Bounds and Algorithms for Parallel Knock-Out Numbers
  
  Broersma, H., Johnson, M., & Paulusma, D. (2007). Upper Bounds and Algorithms for Parallel Knock-Out Numbers. In Structural Information and Communication Complexity (pp. 328-340). https://doi.org/10.1007/978-3-540-72951-8_26
• Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars
  
  Broersma, H., Marchal, B., Paulusma, D., & Salman, A. (2007). Improved Upper Bounds for λ-Backbone Colorings Along Matchings and Stars. In Lecture Notes in Computer Science (pp. 188-199). https://doi.org/10.1007/978-3-540-69507-3_15
• The computational complexity of the parallel knock-out problem
  
  Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006). The computational complexity of the parallel knock-out problem. In LATIN 2006 : theoretical informatics: : 7th Latin American symposium, Valdivia, Chile, March 20-24, 2006 : proceedings. (pp. 250-261). Springer Verlag. https://doi.org/10.1007/11682462_26
• Graph Labelings Derived from Models in Distributed Computing
  
  Chalopin, J., & Paulusma, D. (2006). Graph Labelings Derived from Models in Distributed Computing. In Graph-Theoretic Concepts in Computer Science (pp. 301-312). https://doi.org/10.1007/11917496_27
• On-line coloring of H-free bipartite graphs.
  
  Broersma, H. J., Capponi, A., & Paulusma, D. (2006). On-line coloring of H-free bipartite graphs. In T. Calamoneri, I. Finocchi, & G. F. Italiano (Eds.), Lecture Notes in Computer Science. (pp. 284-295). Springer-Verlag. https://doi.org/10.1007/11758471_28
• Matrix and graph orders derived from locally constrained graph homomorphisms
  
  Fiala, J., Paulusma, D., & Telle, J. A. (2005). Matrix and graph orders derived from locally constrained graph homomorphisms. In J. Jedrzejowicz & A. Szepietowski (Eds.), Mathematical foundations of computer science 2005 : 30th International Symposium, MFCS 2005, Gdansk, Poland, 29 August 29-2September 2005 ; proceedings (pp. 340-351). Springer Verlag. https://doi.org/10.1007/11549345_30
• Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms
  
  Fiala, J., Paulusma, D., & Telle, J. (2005). Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms. In Graph-Theoretic Concepts in Computer Science (pp. 115-126). https://doi.org/10.1007/11604686_11
• The Computational Complexity of the Minimum Weight Processor Assignment Problem
  
  Broersma, H., Paulusma, D., Smit, G., Vlaardingerbroek, F., & Woeginger, G. (2004). The Computational Complexity of the Minimum Weight Processor Assignment Problem. In Graph-Theoretic Concepts in Computer Science (pp. 189-200). https://doi.org/10.1007/978-3-540-30559-0_16
• Run-time assignment of tasks to multiple heterogeneous processors
  
  Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004, January 1). 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). Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture. In 2004 IEEE International Conference on Field-Programmable Technology: Proceedings: December 6-8, 2004, the University of Queensland, Brisbane, Australia. (pp. 421-424). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/fpt.2004.1393315
• The Computational Complexity of the Role Assignment Problem
  
  Fiala, J., & Paulusma, D. (2003). The Computational Complexity of the Role Assignment Problem. In Automata, Languages and Programming (pp. 817-828). https://doi.org/10.1007/3-540-45061-0_64
• The complexity of graph contractions
  
  Levin, A., Paulusma, D., & Woeginger, G. (2003). The complexity of graph contractions. In Graph-Theoretic Concepts in Computer Science (pp. 322-333). https://doi.org/10.1007/978-3-540-39890-5_28

Journal Article

• 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
• Matching Cuts in Graphs of High Girth and H-Free Graphs
  
  Feghali, C., Lucke, F., Paulusma, D., & Ries, B. (2025). Matching Cuts in Graphs of High Girth and H-Free Graphs. Algorithmica. Advance online publication. https://doi.org/10.1007/s00453-025-01318-8
• 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
• Partitioned matching games for international kidney exchange
  
  Benedek, M., Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (2025). Partitioned matching games for international kidney exchange. Mathematical Programming. Advance online publication. https://doi.org/10.1007/s10107-025-02200-9
• 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), Article 14. 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
• Clique-width for hereditary graph classes
  
  Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Clique-width for hereditary graph classes. London Mathematical Society Lecture Note Series, 1-56. https://doi.org/10.1017/9781108649094.002
• 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., 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, Ö.Y., 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, van ’t 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, van ’t 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, van ’t 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, van ’t 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 and 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. van ’t, 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. van ’t, Paulusma, D., & Rooij, J. van. (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. van ’t, & 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. van ’t, 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.
• On Finding Paths Passing through Specified Vertices
  
  Paulusma, D. (2011). On Finding Paths Passing through Specified Vertices.