### Journal Papers

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

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

Algorithmica (2018).

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), 26-32.

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.

arxiv - Surjective
*H*-Colouring: new hardness results.

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

Computability (2018).

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), 75-83.

arxiv doi abstract

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

C. Feghali, M. Johnson.

Journal of Combinatorial Designs 26 (2018), 205-218.

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

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

Discrete Applied Mathematics 236 (2018), 464-471

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

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), 203-224.

pdf 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 96 (2016), 73-85.

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*)-free graphs._{s}, P_{t}

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

The Computer Journal 58 (2015), 3074-3088.

arxiv doi abstract

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

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

- Finding a small number of colourful components.

L. Bulteau, K. K. Dabrowski, G. Fertin, M. Johnson, D. Paulusma, S. Vialette.

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

MFCS 2018

- Connected vertex cover for
*(sP*-free graphs._{1}+P_{5})

M. Johnson, G. Paesani, D. Paulusma.

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

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

Proceedings of ISAAC 2017.

arxiv doi - 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:1-70:14

arxiv doi - 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. Leibniz International Proceedings in Informatics 83, 73:1-73:14

arxiv doi - Surjective
*H*-Colouring: new hardness results.

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

Proceedings of CiE 2017. Lecture Notes in Computer Science 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. Lecture Notes in Computer Science 9538, 100-111.

doi - 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, 395-406.

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

F. Lotfifar, M. Johnson.

Proceedings of Euro-Par 2015. Lecture Notes in Computer Science 9233, 159-170.

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. Lecture Notes in Computer Science 8894, 221-233.

arxiv doi - A reconfigurations analogue of Brooks' Theorem.

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

Proceedings of MFCS 2014. Lecture Notes in Computer Science 8635, 287-298.

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

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

Proceedings of MFCS 2014. Lecture Notes in Computer Science 8635, 396-407.

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

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

Proceedings of AAIM 2014. Lecture Notes in Computer Science 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. Lecture Notes in Computer Science 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.

Proceedings of EuroComb 2011. Electronic Notes in Discrete Mathematics 38, 161-166.

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

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

Proceedings of CSR 2010. Lecture Notes in Computer Science 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, 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, 250-261.

pdf doi - The External Network Problem.

J. van den Heuvel, M. Johnson.

Proceedings of CAAN 2004. Lecture Notes in Computer Science 3405, 114-126.

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: 22 September 2018.