Journal Articles

Johnson, M, Martin, B, Pandey, S, Paulusma, D, Smith, S, van Leeuwen, EJ (2026) Edge Multiway Cut and Node Multiway Cut are Hard for Planar Subcubic Graphs, Algorithmica, 88(6), 66, ISSN: 0178-4617. DOI: 10.1007/s00453-026-01412-5.

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, Algorithmica, 88(1), 7, ISSN: 0178-4617. DOI: 10.1007/s00453-025-01343-7.

Bodlaender, HL, Johnson, M, Martin, B, J. Oostveen, J, Pandey, S, Paulusma, D, Smith, S, Jan van Leeuwen, E (2025) Complexity framework for forbidden subgraphs IV: The Steiner Forest problem, Journal of Computer and System Sciences, 154(2025), 103682, ISSN: 0022-0000. DOI: 10.1016/j.jcss.2025.103682.

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, 103662, ISSN: 0022-0000. DOI: 10.1016/j.jcss.2025.103662.

Johnson, M, Martin, B, J. Oostveen, J, Pandey, S, Paulusma, D, Smith, S, Jan van Leeuwen, E (2025) Complexity framework for forbidden subgraphs I: The framework, Algorithmica, 87(3), pp.429-464, ISSN: 0178-4617. DOI: 10.1007/s00453-024-01289-2.

Berthe, G, Martin, B, Paulusma, D, Smith, S (2023) The Complexity of L(p, q)-Edge-Labelling, Algorithmica, 85(11), pp.3406-3429, ISSN: 0178-4617. DOI: 10.1007/s00453-023-01120-4.

Martin, B, Paulusma, D, Smith, S, van Leeuwen, EJ (2023) Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs, Algorithmica, 85(9), pp.2580-2604, ISSN: 0178-4617. DOI: 10.1007/s00453-023-01109-z.

Martin, B, Paulusma, D, Smith, S, van Leeuwen, EJ (2022) Few induced disjoint paths for H-free graphs, Theoretical Computer Science, 939, pp.182-193, ISSN: 0304-3975. DOI: 10.1016/j.tcs.2022.10.024.

Martin, B, Paulusma, D, Smith, S (2022) Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter, Theoretical Computer Science, 931, pp.104-116, ISSN: 0304-3975. DOI: 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, pp.37-52, ISSN: 0304-3975. DOI: 10.1016/j.tcs.2022.07.009.

Brause, C, Golovach, P, Martin, B, Ochem, P, Paulusma, D, Smith, S (2022) Acyclic, Star, and Injective Colouring: Bounding the Diameter, The Electronic Journal of Combinatorics, 29(2), p.2.43, DOI: 10.37236/10738.

Larose, B, Martin, B, Marković, P, Paulusma, D, Smith, S, Živný, S (2022) QCSP on Reflexive Tournaments, ACM Transactions on Computational Logic, 23(3), pp.1-22, ISSN: 1529-3785. DOI: 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, pp.150-161, ISSN: 0166-218X. DOI: 10.1016/j.dam.2022.02.026.

Kern, W, Martin, B, Paulusma, D, Smith, S, van Leeuwen, EJ (2021) Disjoint paths and connected subgraphs for H-free graphs, Theoretical Computer Science, 898, pp.59-68, ISSN: 0304-3975. DOI: 10.1016/j.tcs.2021.10.019.

Martin, B, Paulusma, D, Smith, S (2021) Hard problems that quickly become very easy, Information Processing Letters, 174, pp.106213-106213, ISSN: 0020-0190. DOI: 10.1016/j.ipl.2021.106213.

Conferences

Ahn, J, Eagling-Vose, T, Lucke, F, Paulusma, D, Smith, S (2025) Finding d-Cuts in claw-free graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025); In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics Lipics, Tainan, Taiwan, pp.1-4, DOI: 10.4230/LIPIcs.ISAAC.2025.4.

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. In Kráľ, D and Milanič, M (ed) 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024; Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Gozd Martuljek, Slovenia, pp.415-429, ISBN: 9783031754098. DOI: 10.1007/978-3-031-75409-8_29.

Lozin, V, Martin, B, Pandey, S, Paulusma, D, Siggers, M, Smith, S, Jan van Leeuwen, E (2024) Complexity framework for forbidden subgraphs II: edge subdivision and the “H”-graphs. In International Symposium on Algorithms and Computation (ISAAC); 35th International Symposium on Algorithms and Computation (ISAAC 2024) - Leibniz International Proceedings in Informatics (LIPIcs), Sydney, Australia, pp.1-47, ISBN: 9783959773546. DOI: 10.4230/LIPIcs.ISAAC.2024.47.

Johnson, M, Martin, B, Pandey, S, Paulusma, D, Smith, S, Jan van Leeuwen, E (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); 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) - International Proceedings in Informatics, LIPIcs, Helsinki, Finland, pp.1-29, ISBN: 9783959773188. DOI: 10.4230/LIPIcs.SWAT.2024.29.

Eagling-Vose, T, Martin, B, Paulusma, D, Smith, S (2024) Graph Homomorphism, Monotone Classes and Bounded Pathwidth. In , Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, pp.233-251, DOI: 10.1007/978-3-031-64309-5_19.

Johnson, M, Martin, B, Pandey, S, Paulusma, D, Smith, S, van Leeuwen, EJ (2023) Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In , Leibniz International Proceedings in Informatics Lipics. DOI: 10.4230/LIPIcs.MFCS.2023.57.

Martin, B, Paulusma, D, Smith, S, van Leeuwen, EJ (2022) Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In , pp.398-411, ISBN: 9783031159138. DOI: 10.1007/978-3-031-15914-5_29.

Berthe, G, Martin, B, Paulusma, D, Smith, S (2022) The Complexity of L(p, q)-Edge-Labelling. In , pp.175-186, ISBN: 9783030967307. DOI: 10.1007/978-3-030-96731-4_15.

Brause, C, Golovach, P, Martin, B, Paulusma, D, Smith, S (2021) Partitioning H-Free Graphs of Bounded Diameter. In , Leibniz International Proceedings in Informatics Lipics. DOI: 10.4230/LIPIcs.ISAAC.2021.21.

Larose, B, Marković, P, Martin, B, Paulusma, D, Smith, S, Živný, S (2021) QCSP on reflexive tournaments. In , Leibniz International Proceedings in Informatics Lipics. DOI: 10.4230/LIPIcs.ESA.2021.58.

Brause, C, Golovach, P, Martin, B, Paulusma, D, Smith, S (2021) Acyclic, Star, and Injective Colouring: Bounding the Diameter. In , pp.336-348, ISBN: 9783030868376. DOI: 10.1007/978-3-030-86838-3_26.

Kern, W, Martin, B, Paulusma, D, Smith, S, van Leeuwen, EJ (2021) Disjoint Paths and Connected Subgraphs for H-Free Graphs. In , pp.414-427, ISBN: 9783030799861. DOI: 10.1007/978-3-030-79987-8_29.

Bok, J, Jedličková, N, Martin, B, Paulusma, D, Smith, S (2021) Injective Colouring for H-Free Graphs. In , pp.18-30, ISBN: 9783030794156. DOI: 10.1007/978-3-030-79416-3_2.

Martin, B, Paulusma, D, Smith, S (2021) Colouring Graphs of Bounded Diameter in the Absence of Small Cycles. In , pp.367-380, ISBN: 9783030752415. DOI: 10.1007/978-3-030-75242-2_26.

Bok, J, Jedličková, 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 Lipics. DOI: 10.4230/LIPIcs.ESA.2020.22.

Martin, B, Paulusma, D, Smith, S (2019) Colouring H-free graphs of bounded diameter. In , Leibniz International Proceedings in Informatics Lipics. DOI: 10.4230/LIPIcs.MFCS.2019.14.

Chapters

Bodlaender, HL, Johnson, M, Martin, B, Oostveen, JJ, Pandey, S, Paulusma, D, Smith, S, van Leeuwen, EJ (2024) Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. In Combinatorial Algorithms, Springer Nature, pp.206-217, DOI: 10.1007/978-3-031-63021-7_16.

Martin, B, Paulusma, D, Smith, S, van Leeuwen, EJ (2022) Few Induced Disjoint Paths for H-Free Graphs. In Combinatorial Optimization, Springer Nature, pp.89-101, DOI: 10.1007/978-3-031-18530-4_7.