### Journal Papers

- Independent feedback vertex sets for graphs of bounded diameter.

M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.

arxiv - Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration.

M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.

arxiv - 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.

arxiv

- Enclosings of decompositions of complete multigraphs in 2-factorizations.

C. Feghali, M. Johnson.

arxiv

- Hereditary graph classes: when the complexities of Colouring and Clique Cover coincide.

A. Blanche, K. K. Dabrowski, M. Johnson, D. Paulusma.

arxiv

- On a conjecture of Mohar concerning Kempe equivalence of regular graphs.

M. Bonamy, N. Bousquet, C. Feghali, M. Johnson.

arxiv

- What graphs are 2-dot product graphs.

M. Johnson, D. Paulusma, E. J. van Leeuwen.

arxiv

- Erdos-Ko-Rado theorems for a family of trees.

C. Feghali, M. Johnson, D. Thomas.

arxiv

- The price of connectivity for cycle transversals.

T. R. Hartinger, M. Johnson, M. Milanic, D.Paulusma.

European Journal of Combinatorics 58 (2016) 203-224.

pdf 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) 331-363.

arxiv doi abstract

- A serial multilevel hypergraph partitioning algorithm.

F. Lotfifar, M. Johnson.

arxiv

- A reconfigurations analogue of Brooks' Theorem and its consequences.

C. Feghali, M. Johnson, D. Paulusma.

Journal of Graph Theory.

arxiv doi abstract

- Smart grid-aware scheduling in data centres.

M. Mäsker, L. Nagel, F. Lotfifar, M. Johnson, A. Brinkmann.

Computer Communications.

pdf doi abstract

- Filling the complexity gaps for colouring planar and bounded degree graphs.

K. K. Dabrowski, F. Dross, M. Johnson, D.Paulusma.

arxiv - Kempe equivalence of colourings of cubic graphs.

C. Feghali, M. Johnson, D. Paulusma.

European Journal of Combinatorics 59 (2017) 1-10.

arxiv doi abstract

- Finding shortest paths between graph colourings.

M. Johnson, D. Kratsch, S. Kratsch, V. Patel, D. Paulusma.

Algorithmica 75 (2016) 295-321.

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) 3074-3088.

arxiv doi abstract

- Knocking out P
_{k}-free graphs.

M. Johnson, D. Paulusma, A. Stewart.

Discrete Applied Mathematics 190-191 (2015), 100-108.

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), 48-55.

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), 132-143.

pdf doi abstract

- Obtaining online ecological colourings by generalizing first-fit.

M. Johnson, V. Patel, D. Paulusma, T. Trunck.

Theory of Computing Systems 54 (2014), 244-260.

pdf doi abstract

- Finding paths between 3-colourings.

L. Cereceda, J. van den Heuvel, M. Johnson.

Journal of Graph Theory 67 (2011), 69-82.

pdf doi abstract

- Mixing 3-colourings in bipartite graphs.

L. Cereceda, J. van den Heuvel, M. Johnson.

European Journal of Combinatorics 30 (2009), 1593-1606.

pdf doi abstract

- Upper bounds and algorithms for parallel knock-out numbers.

H.J. Broersma, M. Johnson, D. Paulusma.

Theoretical Computer Science 410 (2009), 1319-1327.

pdf doi abstract

- Connectedness of the graph of vertex-colourings.

L. Cereceda, J. van den Heuvel, M. Johnson.

Discrete Math. 308 (2008), 913-919.

pdf doi abstract

- The computational complexity of the parallel knock-out problem.

H.J. Broersma, M. Johnson, D. Paulusma, I.A. Stewart.

Theoretical Computer Science 393 (2008), 182-195.

pdf doi abstract

- Transversals of subtree hypergraphs and the source location problem in digraphs.

J. van den Heuvel, M. Johnson.

Networks 51 (2008) 113-119.

pdf doi abstract

- Amalgamations of factorizations of complete graphs.

M. Johnson.

J. Comb. Theory (B) 97 (2007), 597-611.

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), 463-469.

doi abstract

- Amalgamations of factorizations of complete equipartite graphs.

A.J.W Hilton, M. Johnson.

Discrete Math. 284 (2004), 60-77.

pdf doi abstract

- Characterization of graphs with Hall number 2.

Ch. Eslahchi, M. Johnson.

J. Graph Theory 45 (2003), 81-100.

pdf doi abstract

- An algorithm for finding factorizations of complete graphs.

A.J.W Hilton, M. Johnson.

J. Graph Theory 43 (2003), 132-136.

pdf doi abstract

- Amalgamations of connected
*k*-factorizations.

A.J.W Hilton, M. Johnson, C. Rodger, E.B Wantland.

J. Comb. Theory (B) 88 (2003), 267-279.

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), 129-135.

pdf doi abstract

- Some results on the Oberwolfach problem.

A.J.W Hilton, M. Johnson.

J. London Math. Soc. 64 (2001), 513-522.

pdf doi abstract

- Weak critical sets in cyclic Latin squares.

D. Bedford, M. Johnson.

Australas. J. Combin. 23 (2001), 301-316.

pdf abstract

- Weak uniquely completable sets for finite groups.

D. Bedford, M. Johnson.

Bull. London Math. Soc. 32 (2000), 155-162.

doi abstract

### Conference Papers

- Independent feedback vertex set for
*P*-free graphs._{5}

M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.

arxiv - Recognizing graphs close to bipartite graphs.

M. Bonamy, K. K. Dabrowski, C. Feghali, M. Johnson, D. Paulusma.

Proceedings of MFCS 2017.

arxiv - Clique-width for graph classes closed under complementation.

A. Blanche, K. K. Dabrowski, M. Johnson, V. Lozin, D. Paulusma, V. Zamaraev.

Proceedings of MFCS 2017.

arxiv - Surjective H-Colouring: new hardness results.

P. Golovach, M. Johnson, B. Martin, D. Paulusma, A. Stewart.

Proceedings of CiE 2017, LNCS 10307, 270-281.

arxiv doi - Filling the complexity gaps for colouring planar and bounded degree graphs.

K. K. Dabrowski, F. Dross, M. Johnson, D.Paulusma.

Proceedings of IWOCA 2015, LNCS 9538, 100-111.

doi - The price of connectivity for cycle transversals.

T. R. Hartinger, M. Johnson, M. Milanic, D.Paulusma.

Proceedings of MFCS 2015.

pdf doi - A multi-level hypergraph partitioning algorithm using rough set clustering.

F. Lotfifar, M. Johnson.

Proceedings of Euro-Par 2015.

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, 243-249.

arxiv doi - What graphs are 2-dot product graphs.

M. Johnson, D. Paulusma, E. J. van Leeuwen.

Proceedings of EuroComb 2015, Electronic Notes in Discrete Mathematics 49, 705-711.

doi - Smart grid-aware scheduling in data centres.

M. Mäsker, L. Nagel, F. Lotfifar, M. Johnson, A. Brinkmann.

Proceedings of SustainIT 2015, IEEE, 1-9.

pdf doi abstract

- Finding shortest paths between graph colourings.

M. Johnson, D. Kratsch, S. Kratsch, V. Patel, D. Paulusma.

Proceedings of IPEC 2014.

arxiv - A reconfigurations analogue of Brooks' Theorem.

C. Feghali, M. Johnson, D. Paulusma.

Proceedings of MFCS 2014, LNCS 8635, 287-298.

doi - Knocking out P
_{k}-free graphs.

M. Johnson, D. Paulusma, A. Stewart.

Proceedings of MFCS 2014, LNCS 8635, 396-407.

doi - Narrowing the complexity gap for colouring (C
_{s}, P_{t})-free graphs.

S. Huang, M. Johnson, D. Paulusma.

Proceedings of AAIM 2014, LNCS 8546, 162-173.

doi - 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, LNCS 8283, 130-140.

pdf doi - On the diameter of reconfiguration graphs for vertex colourings.

M. Bonamy, M. Johnson, I.M. Lignos, V. Patel, D. Paulusma.

Electronic Notes in Discrete Mathematics 38 (2011), 161-166.

pdf doi - Obtaining online ecological colourings by generalizing first-fit.

M. Johnson, V. Patel, D. Paulusma, T. Trunck.

Proceedings of CSR 2010, LNCS 6072, 240-251.

pdf doi - Finding paths between 3-colourings.

L. Cereceda, J. van den Heuvel, M. Johnson.

Proceedings of IWOCA 2008, 182-196.

pdf - Path factors and parallel knock-out schemes of almost claw-free graphs.

M. Johnson, D. Paulusma, C. Wood.

Proceedings of IWOCA 2008, 27-41.

pdf - Upper bounds and algorithms for parallel knock-out numbers.

H.J. Broersma, M. Johnson, D. Paulusma.

Proceedings of SIROCCO 2007. Lecture Notes in Computer Science 4474, 328-340.

pdf doi - Mixing 3-colourings in bipartite graphs.

L. Cereceda, J. van den Heuvel, M. Johnson.

Proceedings of WG 2007. Lecture Notes in Computer Science 4769 (2007), 166-177.

pdf doi - The computational complexity of the parallel knock-out problem.

H.J. Broersma, M. Johnson D. Paulusma, I.A. Stewart.

Proceedings of LATIN 2006. Lecture Notes in Computer Science 3887 (2006), 250-261.

pdf doi - The External Network Problem.

J. van den Heuvel, M. Johnson.

Lecture Notes in Computer Science 3405 (2005).

pdf doi

### 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: 1 August 2017.