Journal Articles

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

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.