Staff profile

Conference Paper

• 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) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57
• 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) (64:1-64:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.64
• 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) (31:1-31:16). https://doi.org/10.4230/LIPIcs.ISAAC.2023.31
• 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 (88-102). https://doi.org/10.1007/978-3-031-43587-4_7
• 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 (114-128). https://doi.org/10.1007/978-3-031-15914-5_9
• 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 (398-411). https://doi.org/10.1007/978-3-031-15914-5_29
• 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 (89-101). https://doi.org/10.1007/978-3-031-18530-4_7
• 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 (412-424). https://doi.org/10.1007/978-3-031-15914-5_30
• Benedek, M., Biro, P., Kern, W., & Paulusma, D. (2022). Computing balanced solutions for large international kidney exchange schemes. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022) (82-90)
• 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 (175-186). https://doi.org/10.1007/978-3-030-96731-4_15
• 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) (22:1-22:16). https://doi.org/10.4230/lipics.isaac.2022.22
• Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free 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.), . https://doi.org/10.4230/lipics.mfcs.2021.82
• Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Ł. 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 (336-348). https://doi.org/10.1007/978-3-030-86838-3_26
• Martin, B., Paulusma, D., & Smith, S. (2021). Colouring graphs of bounded diameter in the absence of small cycles. In T. Calamoneri, & F. Corò (Eds.), . https://doi.org/10.1007/978-3-030-75242-2_26
• 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 (200-214). https://doi.org/10.1007/978-3-030-83508-8_15
• 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 (229-242). https://doi.org/10.1007/978-3-030-83508-8_17
• 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 (613-624). https://doi.org/10.1007/978-3-030-61792-9_48
• 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 (414-427). https://doi.org/10.1007/978-3-030-79987-8_29
• 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.), . https://doi.org/10.4230/lipics.esa.2021.58
• 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.), . https://doi.org/10.4230/lipics.isaac.2021.21
• 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 (187-199). https://doi.org/10.1007/978-3-030-60440-0_15
• 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 (119-133). https://doi.org/10.1007/978-3-030-60440-0_10
• Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020). Acyclic, star and injective colouring: a complexity picture for H-free graphs. . https://doi.org/10.4230/lipics.esa.2020.22
• 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 (187-199). https://doi.org/10.4230/lipics.ipec.2020.6
• 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) (22:1-22:18). https://doi.org/10.4230/lipics.isaac.2020.22
• 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) (14:1-14:14). https://doi.org/10.4230/lipics.mfcs.2019.14
• Dabrowski, K., Dross, F., Jeong, J., Kanté, M., Kwon, O., Oum, S., & Paulusma, D. (2019). Tree pivot-minors and linear rank-width.
• Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). Independent transversals versus transversals.
• 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 (258-273). https://doi.org/10.1007/978-3-030-25027-0_18
• 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 (413-421)
• 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 (181-195). https://doi.org/10.1007/978-3-030-24766-9_14
• 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
• 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) (5:1-5:13). https://doi.org/10.4230/lipics.isaac.2018.5
• 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 (279-291). https://doi.org/10.1007/978-3-030-00256-5_23
• 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 (125-138). https://doi.org/10.1007/978-3-030-00256-5_11
• 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 (69-81). https://doi.org/10.1007/978-3-319-99660-8_7
• 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 (49:1-49:14). https://doi.org/10.4230/lipics.stacs.2018.49
• 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 (35:1-35:15). https://doi.org/10.4230/lipics.stacs.2018.35
• 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) (61:1-61:14). https://doi.org/10.4230/lipics.esa.2018.61
• 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) (63:1-63:15). https://doi.org/10.4230/lipics.mfcs.2018.63
• 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. https://doi.org/10.4230/lipics.mfcs.2017.70
• 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. https://doi.org/10.4230/lipics.mfcs.2017.73
• 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 (220-233). https://doi.org/10.1007/978-3-319-68705-6_17
• 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
• 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
• 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 (275-288). https://doi.org/10.1007/978-3-319-68705-6_21
• 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 (270-281). https://doi.org/10.1007/978-3-319-58741-7_26
• 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 (470-483). https://doi.org/10.1007/978-3-319-55911-7_34
• 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 (16:1-16:12). https://doi.org/10.4230/lipics.isaac.2017.16
• 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
• 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 (38-49). https://doi.org/10.1007/978-3-319-45587-7_4
• 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 (361-372). https://doi.org/10.1007/978-3-319-44543-4_28
• 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 (253-265). https://doi.org/10.1007/978-3-319-44543-4_20
• 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 (16-30). https://doi.org/10.1007/978-3-662-53174-7_2
• 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 (49-63). https://doi.org/10.1007/978-3-662-53174-7_4
• 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. https://doi.org/10.4230/lipics.mfcs.2016.20
• 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). https://doi.org/10.4230/lipics.swat.2016.4
• 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). https://doi.org/10.4230/lipics.swat.2016.16
• 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 (100-111). https://doi.org/10.1007/978-3-319-29516-9_9
• Johnson, M., van Leeuwen, E., & Paulusma, D. (2015). What graphs are 2-dot product graphs?. . https://doi.org/10.1016/j.endm.2015.06.095
• Feghali, C., Johnson, M., & Paulusma, D. (2015). Kempe equivalence of colourings of cubic graphs. . https://doi.org/10.1016/j.endm.2015.06.034
• Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015). Bounding the clique-width of H-free split graphs. . https://doi.org/10.1016/j.endm.2015.06.069
• 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 (139-150). https://doi.org/10.1007/978-3-662-48054-0_12
• 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 (395-406). https://doi.org/10.1007/978-3-662-48054-0_33
• 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 (243-254). https://doi.org/10.1007/978-3-319-22177-9_19
• 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 (143-156). https://doi.org/10.1007/978-3-319-20297-6_10
• 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 (167-181). https://doi.org/10.1007/978-3-319-18173-8_12
• 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 (194-207). https://doi.org/10.1007/978-3-319-18173-8_14
• 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 (676-688). https://doi.org/10.1007/978-3-319-15579-1_53
• 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 (396-407). https://doi.org/10.1007/978-3-662-44465-8_34
• 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 (287-298). https://doi.org/10.1007/978-3-662-44465-8_25
• 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 (221-233). https://doi.org/10.1007/978-3-319-13524-3_19
• Dabrowski, K. K., Golovach, P. A., Hof, V. 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) (97-108). https://doi.org/10.4230/lipics.fsttcs.2014.97
• 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 (162-173). https://doi.org/10.1007/978-3-319-07956-1_15
• 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 (489-500). https://doi.org/10.1007/978-3-319-08783-2_42
• 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 (225-237). https://doi.org/10.1007/978-3-319-12340-0_19
• Belmonte, R., Hof, V. '. 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 (57-68). https://doi.org/10.1007/978-3-662-44465-8_6
• 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 (127-138). https://doi.org/10.1007/978-3-642-45043-3_12
• 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 (201-212). https://doi.org/10.1007/978-3-642-45043-3_18
• Chaplick, S., Fiala, J., Hof, V. '. 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 (121-132). https://doi.org/10.1007/978-3-642-40164-0_14
• 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) (55-66). https://doi.org/10.4230/lipics.stacs.2013.55
• 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 (288-299). https://doi.org/10.1007/978-3-642-38233-8_24
• Belmonte, R., Hof, V. '. 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 (123-128). https://doi.org/10.1007/978-88-7642-475-5_20
• 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 (177-188). https://doi.org/10.1007/978-3-642-45043-3_16
• Belmonte, R., Golovach, P., Hof, V. '. 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 (16-27). https://doi.org/10.1007/978-3-319-03898-8_3
• 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 (130-140). https://doi.org/10.1007/978-3-642-45030-3_13
• 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 (192-205). https://doi.org/10.1007/978-3-642-45278-9_17
• 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 (320-331). https://doi.org/10.1007/978-3-642-34611-8_32
• 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 (289-300). https://doi.org/10.1007/978-3-642-27660-6_24
• 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 (14-23). https://doi.org/10.1007/978-3-642-35261-4_5
• 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 (495-505). https://doi.org/10.1007/978-3-642-35261-4_52
• 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 (69-80). https://doi.org/10.1007/978-3-642-34611-8_10
• 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 (160-171). https://doi.org/10.1007/978-3-642-30642-6_16
• 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 (515-526). https://doi.org/10.1007/978-3-642-33090-2_45
• 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 (443-454). https://doi.org/10.1007/978-3-642-32589-2_40
• 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 (360-370). https://doi.org/10.1007/978-3-642-31770-5_32
• 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 (455-466). https://doi.org/10.1007/978-3-642-32589-2_41
• 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 (153-164). https://doi.org/10.1007/978-3-642-31155-0_14
• 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
• 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
• 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 (119-130). https://doi.org/10.1007/978-3-642-25870-1_12
• 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 (339-350). https://doi.org/10.1007/978-3-642-22993-0_32
• Heggernes, P., Hof, V. 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 (167-180). https://doi.org/10.1007/978-3-642-19222-7_18
• 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 (261-274). https://doi.org/10.1007/978-3-642-20712-9_20
• 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 (193-204). https://doi.org/10.1007/978-3-642-22953-4_17
• 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 (110-119). https://doi.org/10.1007/978-3-642-25591-5_13
• 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 (561-575). https://doi.org/10.1007/978-3-642-23786-7_43
• 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 (47-60). https://doi.org/10.1007/978-3-642-21581-0_6
• 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 (371-382). https://doi.org/10.4230/lipics.stacs.2010.2469
• 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 (27-41). https://doi.org/10.1016/j.disc.2009.04.022
• 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 (211-221). https://doi.org/10.1007/978-3-642-13562-0_12
• 't, H. P. V., 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 (503-514). https://doi.org/10.1007/978-3-642-11266-9_42
• 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 (122-133). https://doi.org/10.1007/978-3-642-15775-2_11
• 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 (211-221). https://doi.org/10.1007/978-3-642-13562-0_20
• 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 (276-287). https://doi.org/10.1007/978-3-642-13073-1_25
• Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010). Obtaining online ecological colourings by generalizing first-fit. . https://doi.org/10.1007/978-3-642-13182-0_22
• 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 (44-53). https://doi.org/10.1007/978-3-642-11409-0_4
• 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 (1215-1224). https://doi.org/10.1007/978-3-642-10631-6_122
• 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 (514-523). https://doi.org/10.1007/978-3-642-10631-6_53
• 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 (341-352). https://doi.org/10.1007/978-3-642-11409-0_30
• 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 (605-615). https://doi.org/10.1007/978-3-642-10631-6_62
• 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 (95-104). https://doi.org/10.1007/978-3-642-10217-2_12
• Hof, P. V. '., Paulusma, D., & Rooij, J. V. (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 (193-204). https://doi.org/10.1007/978-3-642-03409-1_18
• Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. In Computer science - theory and applications (143-154). https://doi.org/10.1007/978-3-642-03351-3_15
• Hof, P. V., & 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 (415-424). https://doi.org/10.1007/978-3-540-69733-6_41
• 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 (158-167). https://doi.org/10.1007/978-3-540-79709-8_18
• 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 (193-204). https://doi.org/10.1007/978-3-540-85238-4_15
• 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
• 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 (250-261). https://doi.org/10.1007/11682462_26
• 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 (340-351). https://doi.org/10.1007/11549345_30
• Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004). Run-time assignment of tasks to multiple heterogeneous processors.
• 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 (421-424). https://doi.org/10.1109/fpt.2004.1393315

Journal Article

• Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (in press). An algorithmic framework for locally constrained homomorphisms. SIAM Journal on Discrete Mathematics,
• 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
• Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2023). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. European Journal of Combinatorics, https://doi.org/10.1016/j.ejc.2023.103821
• 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
• Lucke, F., Paulusma, D., & Ries, B. (2023). Finding Matching Cuts in H-Free Graphs. Algorithmica, https://doi.org/10.1007/s00453-023-01137-9
• Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, https://doi.org/10.1007/s00453-023-01120-4
• 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
• 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
• 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, https://doi.org/10.1002/jgt.23000
• 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
• 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
• 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
• Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Clique-width for hereditary graph classes. https://doi.org/10.1017/9781108649094.002
• 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
• 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
• Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2018). Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs. Theoretical Computer Science, 746, 49-72. https://doi.org/10.1016/j.tcs.2018.06.023
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Dabrowski, K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, https://doi.org/10.1093/comjnl/bxv096
• 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
• 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
• 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
• Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesař, M. (2015). Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science, 590, 86-95. https://doi.org/10.1016/j.tcs.2015.01.028
• Golovach, P., Heggernes, P., Hof, V. '. P., Manne, F., Paulusma, D., & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica, 72(1), 99-125. https://doi.org/10.1007/s00453-013-9848-2
• 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
• 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
• 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
• 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
• 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
• Cochefert, M., Couturier, J., Golovach, P., & Paulusma, D. (2014). Parameterized algorithms for finding square roots. Algorithmica, https://doi.org/10.1007/s00453-014-9967-4
• 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
• Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2014). Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica, 51(7), 473-497. https://doi.org/10.1007/s00236-014-0204-z
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Belmonte, R., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036
• 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
• 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
• 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
• 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
• 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
• 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
• Fiala, J., Kaminski, M., & Paulusma, D. (2013). A note on contracting claw-free graphs. Discrete Mathematics & Theoretical Computer Science, 15(2), 223-232
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Hof, P. V. '., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. (2012). On graph contractions and induced minors. Discrete Applied Mathematics, 160(6), 799-809. https://doi.org/10.1016/j.dam.2010.05.005
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40-42), 3601-3613. https://doi.org/10.1016/j.tcs.2010.05.041
• 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
• 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
• 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
• Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025
• 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
• Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49), 4834-4843. https://doi.org/10.1016/j.tcs.2009.06.028
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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

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