×

zbMATH — the first resource for mathematics

Johnson, Matthew

Compute Distance To:
Author ID: johnson.matthew Recent zbMATH articles by "Johnson, Matthew"
Published as: Johnson, Matthew; Johnson, Matt
Homepage: http://community.dur.ac.uk/matthew.johnson2/
External Links: MGP · ORCID · dblp
Documents Indexed: 74 Publications since 2000, including 8 Books

Publications by Year

Citations contained in zbMATH Open

44 Publications have been cited 340 times in 191 Documents Cited by Year
Finding paths between 3-colorings. Zbl 1216.05154
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
48
2011
A survey on the computational complexity of coloring graphs with forbidden subgraphs. Zbl 1359.05039
Golovach, Petr A.; Johnson, Matthew; Paulusma, Daniël; Song, Jian
39
2017
Connectedness of the graph of vertex-colourings. Zbl 1133.05053
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
38
2008
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Zbl 1284.05089
Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Daniël
26
2014
Mixing 3-colourings in bipartite graphs. Zbl 1198.05040
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
25
2009
Some results on the Oberwolfach problem. Zbl 1012.05135
Hilton, A. J. W.; Johnson, Matthew
14
2001
A reconfigurations analogue of Brooks’ theorem and its consequences. Zbl 1350.05034
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
12
2016
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
12
2016
Amalgamations of connected \(k\)-factorizations. Zbl 1033.05084
Hilton, A. J. W.; Johnson, Matthew; Rodger, C. A.; Wantland, E. B.
9
2003
Transversals of subtree hypergraphs and the source location problem in digraphs. Zbl 1180.05116
van den Heuvel, Jan; Johnson, Matthew
7
2008
Characterization of graphs with Hall number 2. Zbl 1033.05040
Eslahchi, Changiz; Johnson, Matthew
7
2004
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
Independent feedback vertex sets for graphs of bounded diameter. Zbl 1422.68104
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
7
2018
Amalgamations of factorizations of complete graphs. Zbl 1153.05055
Johnson, Matthew
6
2007
Independent feedback vertex set for \(P_5\)-free graphs. Zbl 1422.68105
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
6
2019
The price of connectivity for cycle transversals. Zbl 1343.05157
Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
6
2016
Finding paths between 3-colourings. Zbl 1235.05135
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
5
2009
Kempe equivalence of colourings of cubic graphs. Zbl 1348.05074
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
5
2017
Finding paths between graph colourings: Computational complexity and possible distances. Zbl 1341.05063
Bonsma, Paul; Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
4
2007
An algorithm for finding factorizations of complete graphs. Zbl 1015.05075
Hilton, A. J. W.; Johnson, Matthew
4
2003
A reconfigurations analogue of Brooks’ theorem. Zbl 1426.05042
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
4
2014
Hereditary graph classes: when the complexities of coloring and clique cover coincide. Zbl 1417.05060
Blanché, Alexandre; Dabrowski, Konrad K.; Johnson, Matthew; Paulusma, Daniël
4
2019
On a conjecture of Mohar concerning Kempe equivalence of regular graphs. Zbl 1404.05049
Bonamy, Marthe; Bousquet, Nicolas; Feghali, Carl; Johnson, Matthew
4
2019
Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity. Zbl 1380.68219
Chiarelli, Nina; Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
4
2018
Erdös-Ko-Rado theorems for a family of trees. Zbl 1377.05031
Feghali, Carl; Johnson, Matthew; Thomas, Daniel
4
2018
The computational complexity of the parallel knock-out problem. Zbl 1136.68028
Broersma, Hajo; Johnson, Matthew; Paulusma, Daniël; Stewart, Iain A.
3
2008
Mixing 3-colourings in bipartite graphs. Zbl 1141.68521
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
3
2007
Cycle decompositions of the complete graph. Zbl 1174.05412
Hilton, A. J. W.; Johnson, Matthew
3
2006
Path factors and parallel knock-out schemes of almost claw-free graphs. Zbl 1219.05140
Johnson, Matthew; Paulusma, Daniël; Wood, Chantal
3
2010
Narrowing the complexity gap for colouring \((C_{s},P_{t})\)-free graphs. Zbl 1445.68110
Huang, Shenwei; Johnson, Matthew; Paulusma, Daniël
3
2014
Surjective \(H\)-colouring: new hardness results. Zbl 1425.05055
Golovach, Petr A.; Johnson, Matthew; Martin, Barnaby; Paulusma, Daniël; Stewart, Anthony
2
2019
On the diameter of reconfiguration graphs for vertex colourings. Zbl 1274.05144
Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Daniël
2
2011
A multi-level hypergraph partitioning algorithm using rough set clustering. Zbl 1377.05186
Lotfifar, Foad; Johnson, Matthew
2
2015
Recognizing graphs close to bipartite graphs. Zbl 1441.68167
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
2
2017
The computational complexity of the parallel knock-out problem. Zbl 1145.68433
Broersma, Hajo; Johnson, Matthew; Paulusma, Daniël; Stewart, Iain A.
1
2006
Upper bounds and algorithms for parallel knock-out numbers. Zbl 1164.68026
Broersma, Hajo; Johnson, Matthew; Paulusma, Daniël
1
2009
Weak critical sets in cyclic Latin squares. Zbl 0977.05023
Johnson, Matthew; Bedford, David
1
2001
Knocking out \(P _{k }\)-free graphs. Zbl 1426.68125
Johnson, Matthew; Paulusma, Daniël; Stewart, Anthony
1
2014
Connected vertex cover for \((sP_1+P_5)\)-free graphs. Zbl 1436.68245
Johnson, Matthew; Paesani, Giacomo; Paulusma, Daniël
1
2020
The price of connectivity for cycle transversals. Zbl 1455.05076
Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
1
2015
Connected vertex cover for \((sP_1+P_5)\)-free graphs. Zbl 1436.68244
Johnson, Matthew; Paesani, Giacomo; Paulusma, Daniël
1
2018
Kempe equivalence of colourings of cubic graphs. Zbl 1346.05065
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
1
2015
Clique-width for graph classes closed under complementation. Zbl 1441.05167
Blanché, Alexandre; Dabrowski, Konrad K.; Johnson, Matthew; Lozin, Vadim V.; Paulusma, Daniël; Zamaraev, Viktor
1
2020
Enclosings of decompositions of complete multigraphs in 2-factorizations. Zbl 1396.05091
Feghali, Carl; Johnson, Matthew
1
2018
Connected vertex cover for \((sP_1+P_5)\)-free graphs. Zbl 1436.68245
Johnson, Matthew; Paesani, Giacomo; Paulusma, Daniël
1
2020
Clique-width for graph classes closed under complementation. Zbl 1441.05167
Blanché, Alexandre; Dabrowski, Konrad K.; Johnson, Matthew; Lozin, Vadim V.; Paulusma, Daniël; Zamaraev, Viktor
1
2020
Independent feedback vertex set for \(P_5\)-free graphs. Zbl 1422.68105
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
6
2019
Hereditary graph classes: when the complexities of coloring and clique cover coincide. Zbl 1417.05060
Blanché, Alexandre; Dabrowski, Konrad K.; Johnson, Matthew; Paulusma, Daniël
4
2019
On a conjecture of Mohar concerning Kempe equivalence of regular graphs. Zbl 1404.05049
Bonamy, Marthe; Bousquet, Nicolas; Feghali, Carl; Johnson, Matthew
4
2019
Surjective \(H\)-colouring: new hardness results. Zbl 1425.05055
Golovach, Petr A.; Johnson, Matthew; Martin, Barnaby; Paulusma, Daniël; Stewart, Anthony
2
2019
Independent feedback vertex sets for graphs of bounded diameter. Zbl 1422.68104
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
7
2018
Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity. Zbl 1380.68219
Chiarelli, Nina; Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
4
2018
Erdös-Ko-Rado theorems for a family of trees. Zbl 1377.05031
Feghali, Carl; Johnson, Matthew; Thomas, Daniel
4
2018
Connected vertex cover for \((sP_1+P_5)\)-free graphs. Zbl 1436.68244
Johnson, Matthew; Paesani, Giacomo; Paulusma, Daniël
1
2018
Enclosings of decompositions of complete multigraphs in 2-factorizations. Zbl 1396.05091
Feghali, Carl; Johnson, Matthew
1
2018
A survey on the computational complexity of coloring graphs with forbidden subgraphs. Zbl 1359.05039
Golovach, Petr A.; Johnson, Matthew; Paulusma, Daniël; Song, Jian
39
2017
Kempe equivalence of colourings of cubic graphs. Zbl 1348.05074
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
5
2017
Recognizing graphs close to bipartite graphs. Zbl 1441.68167
Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
2
2017
A reconfigurations analogue of Brooks’ theorem and its consequences. Zbl 1350.05034
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
12
2016
Finding shortest paths between graph colourings. Zbl 1350.68148
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
12
2016
The price of connectivity for cycle transversals. Zbl 1343.05157
Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
6
2016
A multi-level hypergraph partitioning algorithm using rough set clustering. Zbl 1377.05186
Lotfifar, Foad; Johnson, Matthew
2
2015
The price of connectivity for cycle transversals. Zbl 1455.05076
Hartinger, Tatiana R.; Johnson, Matthew; Milanič, Martin; Paulusma, Daniël
1
2015
Kempe equivalence of colourings of cubic graphs. Zbl 1346.05065
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
1
2015
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Zbl 1284.05089
Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Daniël
26
2014
Finding shortest paths between graph colourings. Zbl 1341.68062
Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël
7
2014
A reconfigurations analogue of Brooks’ theorem. Zbl 1426.05042
Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
4
2014
Narrowing the complexity gap for colouring \((C_{s},P_{t})\)-free graphs. Zbl 1445.68110
Huang, Shenwei; Johnson, Matthew; Paulusma, Daniël
3
2014
Knocking out \(P _{k }\)-free graphs. Zbl 1426.68125
Johnson, Matthew; Paulusma, Daniël; Stewart, Anthony
1
2014
Finding paths between 3-colorings. Zbl 1216.05154
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
48
2011
On the diameter of reconfiguration graphs for vertex colourings. Zbl 1274.05144
Bonamy, Marthe; Johnson, Matthew; Lignos, Ioannis; Patel, Viresh; Paulusma, Daniël
2
2011
Path factors and parallel knock-out schemes of almost claw-free graphs. Zbl 1219.05140
Johnson, Matthew; Paulusma, Daniël; Wood, Chantal
3
2010
Mixing 3-colourings in bipartite graphs. Zbl 1198.05040
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
25
2009
Finding paths between 3-colourings. Zbl 1235.05135
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
5
2009
Upper bounds and algorithms for parallel knock-out numbers. Zbl 1164.68026
Broersma, Hajo; Johnson, Matthew; Paulusma, Daniël
1
2009
Connectedness of the graph of vertex-colourings. Zbl 1133.05053
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
38
2008
Transversals of subtree hypergraphs and the source location problem in digraphs. Zbl 1180.05116
van den Heuvel, Jan; Johnson, Matthew
7
2008
The computational complexity of the parallel knock-out problem. Zbl 1136.68028
Broersma, Hajo; Johnson, Matthew; Paulusma, Daniël; Stewart, Iain A.
3
2008
Amalgamations of factorizations of complete graphs. Zbl 1153.05055
Johnson, Matthew
6
2007
Finding paths between graph colourings: Computational complexity and possible distances. Zbl 1341.05063
Bonsma, Paul; Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
4
2007
Mixing 3-colourings in bipartite graphs. Zbl 1141.68521
Cereceda, Luis; van den Heuvel, Jan; Johnson, Matthew
3
2007
Cycle decompositions of the complete graph. Zbl 1174.05412
Hilton, A. J. W.; Johnson, Matthew
3
2006
The computational complexity of the parallel knock-out problem. Zbl 1145.68433
Broersma, Hajo; Johnson, Matthew; Paulusma, Daniël; Stewart, Iain A.
1
2006
Characterization of graphs with Hall number 2. Zbl 1033.05040
Eslahchi, Changiz; Johnson, Matthew
7
2004
Amalgamations of connected \(k\)-factorizations. Zbl 1033.05084
Hilton, A. J. W.; Johnson, Matthew; Rodger, C. A.; Wantland, E. B.
9
2003
An algorithm for finding factorizations of complete graphs. Zbl 1015.05075
Hilton, A. J. W.; Johnson, Matthew
4
2003
Some results on the Oberwolfach problem. Zbl 1012.05135
Hilton, A. J. W.; Johnson, Matthew
14
2001
Weak critical sets in cyclic Latin squares. Zbl 0977.05023
Johnson, Matthew; Bedford, David
1
2001
all top 5

Cited by 275 Authors

31 Paulusma, Daniël
25 Johnson, Matthew
15 Feghali, Carl
13 Ito, Takehiro
9 Bonamy, Marthe
9 Dabrowski, Konrad Kazimierz
7 Bahmanian, M. Amin
7 Bryant, Darryn E.
7 Chudnovsky, Maria
7 Kamiński, Marcin Marek
7 Suzuki, Akira
6 Bonsma, Paul S.
6 Milanič, Martin
6 Mouawad, Amer E.
6 Nishimura, Naomi
6 Zhong, Mingxian
6 Zhou, Xiao
5 Bousquet, Nicolas
5 Demaine, Erik D.
5 Hilton, Anthony J. W.
5 Schaudt, Oliver
4 Brewster, Richard C.
4 Cereceda, Luis
4 Danziger, Peter
4 Lozin, Vadim Vladislavovich
4 Malyshev, Dmitry S.
4 Raman, Venkatesh
4 Rzążewski, Paweł
4 Wrochna, Marcin
3 Asplund, John
3 Buratti, Marco
3 Goedgebeur, Jan
3 Haas, Ruth
3 Horsley, Daniel
3 Huang, Shenwei
3 Lee, Jae-Baek
3 Medvedev, Paul
3 Noel, Jonathan Andrew
3 Ono, Hirotaka
3 Paesani, Giacomo
3 Ries, Bernard
3 Rodger, Christopher Andrew
3 Seyffarth, Karen
3 Siggers, Mark H.
3 Stein, Maya Jakobine
3 Traetta, Tommaso
3 van den Heuvel, Jan
3 Van Leeuwen, Erik Jan
2 Blanché, Alexandre
2 Borg, Peter
2 Broersma, Hajo J.
2 Burgess, Andrea C.
2 Cropper, Mathew Maurice
2 Dvořák, Zdeněk
2 Estrugo, Emiliano J. J.
2 Gaspers, Serge
2 Hartinger, Tatiana Romina
2 Hatanaka, Tatsuhiko
2 Hoffman, Dean G.
2 Johnson, Peter D. jun.
2 Karthick, T.
2 Kobayashi, Yusuke
2 Lehel, Jeno
2 Lima, Paloma T.
2 Maceli, Peter
2 Maenhaut, Barbara M.
2 Mendelsohn, Eric
2 Mynhardt, Christina M.
2 Novotná, Jana
2 Okrasa, Karolina
2 Osawa, Hiroki
2 Ozkan, Sibel
2 Pastine, Adrián
2 Patel, Viresh
2 Pathak, Vinayak
2 Perarnau, Guillem
2 Picouleau, Christophe
2 Russell, Heather M.
2 Spirkl, Sophie Theresa
2 Stacho, Juraj
2 Tuza, Zsolt
2 Uehara, Ryuhei
2 Werner, Brett M.
2 Yamada, Takeshi
2 Zamaraev, Victor A.
2 Zhou, Sizhong
1 Abu-Khzam, Faisal N.
1 Adams, Peter J.
1 Ait-Ferhat, Dehia
1 Alikhani, Saeid
1 Allagan, Julian A. D.
1 Ardal, Hayri
1 Arora, Pranav
1 Atminas, Aistis
1 Bang-Jensen, Jørgen
1 Banik, Aritra
1 Bárász, Mihály
1 Becker, Johanna
1 Beier, Julie
1 Belmonte, Rémy
...and 175 more Authors

Citations by Year