show/hide all abstracts

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 (Cs, Pt)-free graphs.
    S. Huang, M. Johnson, D. Paulusma.
    The Computer Journal 58 (2015) 3074-3088.
    arxiv  doi  abstract
  • Knocking out Pk-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 P5-free graphs.
    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 Pk-free graphs.
    M. Johnson, D. Paulusma, A. Stewart.
    Proceedings of MFCS 2014, LNCS 8635, 396-407.
    doi
  • Narrowing the complexity gap for colouring (Cs, Pt)-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.