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.
    Theoretical Computer Science (2017) to appear.
    arxiv  doi  abstract
  • 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: 6 October 2017.