Journal Papers
 Graph isomorphism for (H_{1},H_{2})free graphs: an almost complete dichotomy.
M. Bonamy, N. Bousquet, K.K. Dabrowski, M. Johnson, D. Paulusma, T. Pierron.
Algorithmica 83 (2021), 822852.
arxiv doi abstract
 Steiner trees for hereditary graph classes: a treewidth perspective.
H. Bodlaender, N. Brettell, M. Johnson, G. Paesani, D. Paulusma, E. J. van Leeuwen.
Theoretical Computer Science 867 (2021), 3039.
arxiv doi abstract
 On cycle transversals and their connected variants in the absence of a small linear forest.
K. K. Dabrowski, C. Feghali, M. Johnson, G. Paesani, D. Paulusma, P. Rzążewski .
Algorithmica 82 (2020), 28412866.
arxiv doi abstract
 Cliquewidth for graph classes closed under complementation.
A. Blanche, K. K. Dabrowski, M. Johnson, V. Lozin, D. Paulusma, V. Zamaraev.
SIAM Journal on Discrete Mathematics 34 (2020), 11071147
arxiv doi abstract
 Independent feedback vertex set for P_{5}free graphs.
M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.
Algorithmica 81 (2019), 13421369.
arxiv doi abstract
 Cliquewidth for hereditary graph classes.
K.K. Dabrowski, M. Johnson and D. Paulusma.
London Mathematical Society Lecture Note Series 456 (2019) 156.
arxiv doi abstract
 Independent feedback vertex sets for graphs of bounded diameter.
M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.
Information Processing Letters 131 (2018), 2632.
arxiv doi abstract
 Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration.
M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.
Journal of Graph Theory 98 (2021), 81109.
arxiv doi abstract
 Surjective HColouring: new hardness results.
P. Golovach, M. Johnson, B. Martin, D. Paulusma, A. Stewart.
Computability (2018).
arxiv doi abstract
 Connected vertex cover for (sP_{1}+P_{5})free graphs.
M. Johnson, G. Paesani, D. Paulusma.
Algorithmica 82 (2020), 2040.
arxiv doi abstract
 Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity.
N. Chiarelli, T. R. Hartinger, M. Johnson, M. Milanic, D. Paulusma.
Theoretical Computer Science 705 (2018), 7583.
arxiv doi abstract
 Enclosings of decompositions of complete multigraphs in 2factorizations.
C. Feghali, M. Johnson.
Journal of Combinatorial Designs 26 (2018), 205218.
arxiv doi abstract
 Hereditary graph classes: when the complexities of Colouring and Clique Cover coincide.
A. Blanche, K. K. Dabrowski, M. Johnson, D. Paulusma.
arxiv doi abstract
 On a conjecture of Mohar concerning Kempe equivalence of regular graphs.
M. Bonamy, N. Bousquet, C. Feghali, M. Johnson.
Journal of Combinatorial Theory, Series B (2018).
arxiv doi abstract
 What graphs are 2dot product graphs.
M. Johnson, D. Paulusma, E. J. van Leeuwen.
arxiv
 ErdosKoRado theorems for a family of trees.
C. Feghali, M. Johnson, D. Thomas.
Discrete Applied Mathematics 236 (2018), 464471
arxiv doi abstract
 A survey on the computational complexity of colouring graphs with forbidden subgraphs.
P. A. Golovach, M. Johnson, D. Paulusma, J. Song.
Journal of Graph Theory 84 (2017), 331363.
arxiv doi abstract
 The price of connectivity for cycle transversals.
T. R. Hartinger, M. Johnson, M. Milanic, D.Paulusma.
European Journal of Combinatorics 58 (2016), 203224.
pdf doi abstract
 A reconfigurations analogue of Brooks' Theorem and its consequences.
C. Feghali, M. Johnson, D. Paulusma.
Journal of Graph Theory 83 (2016), 340358.
arxiv doi abstract
 Smart gridaware scheduling in data centres.
M. Mäsker, L. Nagel, F. Lotfifar, M. Johnson, A. Brinkmann.
Computer Communications 96 (2016), 7385.
pdf doi abstract
 Filling the complexity gaps for colouring planar and bounded degree graphs.
K. K. Dabrowski, F. Dross, M. Johnson, D.Paulusma.
Journal of Graph Theory 92 (2019), 377393.
arxiv doi abstract
 Kempe equivalence of colourings of cubic graphs.
C. Feghali, M. Johnson, D. Paulusma.
European Journal of Combinatorics 59 (2017), 110.
arxiv doi abstract
 Finding shortest paths between graph colourings.
M. Johnson, D. Kratsch, S. Kratsch, V. Patel, D. Paulusma.
Algorithmica 75 (2016), 295321.
arxiv doi abstract
 Narrowing the complexity gap for colouring (C_{s}, P_{t})free graphs.
S. Huang, M. Johnson, D. Paulusma.
The Computer Journal 58 (2015), 30743088.
arxiv doi abstract
 Knocking out P_{k}free graphs.
M. Johnson, D. Paulusma, A. Stewart.
Discrete Applied Mathematics 190191 (2015), 100108.
pdf doi abstract
 Algorithms to measure diversity and clustering in social networks through dot product graphs.
M. Johnson, D. Paulusma, E. J. van Leeuwen.
Social Networks 41 (2015), 4855.
pdf doi abstract
 Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.
M. Bonamy, M. Johnson, I.M. Lignos, V. Patel, D. Paulusma.
Journal of Combinatorial Optimization 27 (2014), 132143.
pdf doi abstract
 Obtaining online ecological colourings by generalizing firstfit.
M. Johnson, V. Patel, D. Paulusma, T. Trunck.
Theory of Computing Systems 54 (2014), 244260.
pdf doi abstract
 Finding paths between 3colourings.
L. Cereceda, J. van den Heuvel, M. Johnson.
Journal of Graph Theory 67 (2011), 6982.
pdf doi abstract
 Mixing 3colourings in bipartite graphs.
L. Cereceda, J. van den Heuvel, M. Johnson.
European Journal of Combinatorics 30 (2009), 15931606.
pdf doi abstract
 Upper bounds and algorithms for parallel knockout numbers.
H.J. Broersma, M. Johnson, D. Paulusma.
Theoretical Computer Science 410 (2009), 13191327.
pdf doi abstract
 Connectedness of the graph of vertexcolourings.
L. Cereceda, J. van den Heuvel, M. Johnson.
Discrete Math. 308 (2008), 913919.
pdf doi abstract
 The computational complexity of the parallel knockout problem.
H.J. Broersma, M. Johnson, D. Paulusma, I.A. Stewart.
Theoretical Computer Science 393 (2008), 182195.
pdf doi abstract
 Transversals of subtree hypergraphs and the source location problem in digraphs.
J. van den Heuvel, M. Johnson.
Networks 51 (2008) 113119.
pdf doi abstract
 Amalgamations of factorizations of complete graphs.
M. Johnson.
J. Comb. Theory (B) 97 (2007), 597611.
pdf doi abstract
 Cycle decompositions of the complete graph.
A.J.W Hilton, M. Johnson.
Ars Combinatoria 81 (2007).
pdf abstract
 Finding paths between graph colourings: computational complexity and possible distances.
P. Bonsma, L. Cereceda, J. van den Heuvel, M. Johnson.
Electronic Notes in Discrete Mathematics 29 (2007), 463469.
doi abstract
 Amalgamations of factorizations of complete equipartite graphs.
A.J.W Hilton, M. Johnson.
Discrete Math. 284 (2004), 6077.
pdf doi abstract
 Characterization of graphs with Hall number 2.
Ch. Eslahchi, M. Johnson.
J. Graph Theory 45 (2003), 81100.
pdf doi abstract
 An algorithm for finding factorizations of complete graphs.
A.J.W Hilton, M. Johnson.
J. Graph Theory 43 (2003), 132136.
pdf doi abstract
 Amalgamations of connected kfactorizations.
A.J.W Hilton, M. Johnson, C. Rodger, E.B Wantland.
J. Comb. Theory (B) 88 (2003), 267279.
ps doi abstract
 Defining sets for Latin squares given that they are based on groups.
D. Bedford, M. Johnson, M. Ollis.
European J. of Combinatorics 24 (2003), 129135.
pdf doi abstract
 Some results on the Oberwolfach problem.
A.J.W Hilton, M. Johnson.
J. London Math. Soc. 64 (2001), 513522.
pdf doi abstract
 Weak critical sets in cyclic Latin squares.
D. Bedford, M. Johnson.
Australas. J. Combin. 23 (2001), 301316.
pdf abstract
 Weak uniquely completable sets for finite groups.
D. Bedford, M. Johnson.
Bull. London Math. Soc. 32 (2000), 155162.
doi abstract
Conference Papers
 Computing weighted subset transversals in Hfree graphs.
N. Brettell, M. Johnson, D. Paulusma.
arxiv
 Computing subset transversals in Hfree graphs.
N. Brettell, M. Johnson, G. Paesani, D. Paulusma.
Proceedings of WG 2020. Lecture Notes in Computer Science 12301, 187199.
arxiv doi
 Steiner trees for hereditary graph classes.
H. Bodlaender, N. Brettell, M. Johnson, G. Paesani, D. Paulusma, E. J. van Leeuwen.
LATIN 2020 Proceedings of LATIN 2020. Lecture Notes in Computer Science 12118, 613624.
arxiv doi
 Graph isomorphism for (H_{1},H_{2})free graphs: an almost complete dichotomy.
M. Bonamy, K.K. Dabrowski, M. Johnson, D. Paulusma.
Proceedings of WADS 2019. Lecture Notes in Computer Science 11646, 181195.
arxiv doi
 Independent transversals versus transversals.
K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma, V. Zamaraev.
Proceedings of EuroComb 2019. Acta Mathematica Universitatis Comenianae 88, 577583.
link
 On cycle transversals and their connected variants in the absence of a small linear forest.
C. Feghali, M. Johnson, G. Paesani and D. Paulusma.
Proceedings of FCT 2019. Lecture Notes in Computer Science 11651, 258273.
doi extended version
 Finding a small number of colourful components.
L. Bulteau, K. K. Dabrowski, G. Fertin, M. Johnson, D. Paulusma, S. Vialette.
Proceedings of CPM 2019. Leibniz International Proceedings in Informatics 128, 20:120:14
arxiv doi
 On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.
K.K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma, V. Zamaraev.
Proceedings of MFCS 2018. Leibniz International Proceedings in Informatics 83, 70:170:14
arxiv doi
 Connected vertex cover for (sP_{1}+P_{5})free graphs.
M. Johnson, G. Paesani, D. Paulusma.
Proceedings of WG 2018. Lecture Notes in Computer Science 11159, 279291.
arxiv doi extended version
 Independent feedback vertex set for P_{5}free graphs.
M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.
Proceedings of ISAAC 2017.
arxiv doi extended version
 Recognizing graphs close to bipartite graphs.
M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.
Proceedings of MFCS 2017. Leibniz International Proceedings in Informatics 83, 70:170:14
arxiv doi
 Cliquewidth for graph classes closed under complementation.
A. Blanche, K. K. Dabrowski, M. Johnson, V. Lozin, D. Paulusma, V. Zamaraev.
Proceedings of MFCS 2017. Leibniz International Proceedings in Informatics 83, 73:173:14
arxiv doi extended version
 Surjective HColouring: new hardness results.
P. Golovach, M. Johnson, B. Martin, D. Paulusma, A. Stewart.
Proceedings of CiE 2017. Lecture Notes in Computer Science 10307, 270281.
arxiv doi extended version
 Filling the complexity gaps for colouring planar and bounded degree graphs.
K. K. Dabrowski, F. Dross, M. Johnson, D.Paulusma.
Proceedings of IWOCA 2015. Lecture Notes in Computer Science 9538, 100111.
doi extended version
 The price of connectivity for cycle transversals.
T. R. Hartinger, M. Johnson, M. Milanic, D.Paulusma.
Proceedings of MFCS 2015. Lecture Notes in Computer Science 9235, 395406.
pdf doi extended version
 A multilevel hypergraph partitioning algorithm using rough set clustering.
F. Lotfifar, M. Johnson.
Proceedings of EuroPar 2015. Lecture Notes in Computer Science 9233, 159170.
pdf doi abstract
 Kempe equivalence of colourings of cubic graphs.
C. Feghali, M. Johnson, D. Paulusma.
Proceedings of EuroComb 2015. Electronic Notes in Discrete Mathematics 49, 243249.
arxiv doi extended version
 What graphs are 2dot product graphs.
M. Johnson, D. Paulusma, E. J. van Leeuwen.
Proceedings of EuroComb 2015. Electronic Notes in Discrete Mathematics 49, 705711.
doi
 Smart gridaware scheduling in data centres.
M. Mäsker, L. Nagel, F. Lotfifar, M. Johnson, A. Brinkmann.
Proceedings of SustainIT 2015, IEEE, 19.
pdf doi extended version
 Finding shortest paths between graph colourings.
M. Johnson, D. Kratsch, S. Kratsch, V. Patel, D. Paulusma.
Proceedings of IPEC 2014. Lecture Notes in Computer Science 8894, 221233.
arxiv doi extended version
 A reconfigurations analogue of Brooks' Theorem.
C. Feghali, M. Johnson, D. Paulusma.
Proceedings of MFCS 2014. Lecture Notes in Computer Science 8635, 287298.
doi extended version
 Knocking out P_{k}free graphs.
M. Johnson, D. Paulusma, A. Stewart.
Proceedings of MFCS 2014. Lecture Notes in Computer Science 8635, 396407.
doi extended version
 Narrowing the complexity gap for colouring (C_{s}, P_{t})free graphs.
S. Huang, M. Johnson, D. Paulusma.
Proceedings of AAIM 2014. Lecture Notes in Computer Science 8546, 162173.
doi extended version
 Algorithms to measure diversity and clustering in social networks through dot product graphs.
M. Johnson, D. Paulusma, E. J. van Leeuwen.
Proceedings of ISAAC 2013. Lecture Notes in Computer Science 8283, 130140.
pdf doi extended version
 On the diameter of reconfiguration graphs for vertex colourings.
M. Bonamy, M. Johnson, I.M. Lignos, V. Patel, D. Paulusma.
Proceedings of EuroComb 2011. Electronic Notes in Discrete Mathematics 38, 161166.
pdf doi extended version
 Obtaining online ecological colourings by generalizing firstfit.
M. Johnson, V. Patel, D. Paulusma, T. Trunck.
Proceedings of CSR 2010. Lecture Notes in Computer Science 6072, 240251.
pdf doi extended version
 Finding paths between 3colourings.
L. Cereceda, J. van den Heuvel, M. Johnson.
Proceedings of IWOCA 2008, 182196.
pdf extended version
 Path factors and parallel knockout schemes of almost clawfree graphs.
M. Johnson, D. Paulusma, C. Wood.
Proceedings of IWOCA 2008, 2741.
pdf
 Upper bounds and algorithms for parallel knockout numbers.
H.J. Broersma, M. Johnson, D. Paulusma.
Proceedings of SIROCCO 2007. Lecture Notes in Computer Science 4474, 328340.
pdf doi extended version
 Mixing 3colourings in bipartite graphs.
L. Cereceda, J. van den Heuvel, M. Johnson.
Proceedings of WG 2007. Lecture Notes in Computer Science 4769, 166177.
pdf doi extended version
 The computational complexity of the parallel knockout problem.
H.J. Broersma, M. Johnson D. Paulusma, I.A. Stewart.
Proceedings of LATIN 2006. Lecture Notes in Computer Science 3887, 250261.
pdf doi extended version
 The external network problem.
J. van den Heuvel, M. Johnson.
Proceedings of CAAN 2004. Lecture Notes in Computer Science 3405, 114126.
pdf doi extended version
Edited Volumes
 Selected papers from the 4th Algorithms and Complexity in Durham Workshop, ACiD 2010.
I.A. Stewart, D. Paulusma, M. Johnson.
J. Discrete Algorithms 12 (2012)
doi

Selected papers from the 3rd Algorithms and Complexity in Durham Workshop, ACiD 2007.
H.J Broersma, S.S Dantchev, M. Johnson, S. Szeider.
J. Discrete Algorithms 8 (2010).
doi

Selected papers from the 2nd Algorithms and Complexity in Durham Workshop, ACiD 2006.
H.J Broersma, S.S Dantchev, M. Johnson, S. Szeider.
J. Discrete Algorithms 7 (2009).
doi

Selected papers from the 1st Algorithms and Complexity in Durham Workshop, ACiD 2005.
H.J Broersma, S.S Dantchev, M. Johnson, S. Szeider.
J. Discrete Algorithms 6 (2008).
doi

Algorithms and Complexity in Durham 2007, Proceedings of the Third ACiD Workshop.
H.J Broersma, S.S Dantchev, M. Johnson, S. Szeider.
Texts in Algorithmics 9, College Publications, London, 2007.

Algorithms and Complexity in Durham 2006, Proceedings of the Second ACiD Workshop.
H.J Broersma, S.S Dantchev, M. Johnson, S. Szeider.
Texts in Algorithmics 7, College Publications, London, 2006.

Algorithms and Complexity in Durham 2005, Proceedings of the First ACiD Workshop.
H.J Broersma, S.S Dantchev, M. Johnson, S. Szeider.
Texts in Algorithmics 4, College Publications, London, 2005.
Last change: 27 August 2021