Matthew Johnson

From MaRDI portal
Person:309789

Available identifiers

zbMath Open johnson.matthewMaRDI QIDQ309789

List of research outcomes

PublicationDate of PublicationType
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal2024-01-23Paper
Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration2023-10-04Paper
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem2023-05-02Paper
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs2023-05-01Paper
Computing subset transversals in \(H\)-free graphs2022-12-21Paper
Complexity Framework For Forbidden Subgraphs I: The Framework2022-11-23Paper
Steiner trees for hereditary graph classes2022-10-13Paper
Finding a Small Number of Colourful Components2022-07-18Paper
Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs2022-05-16Paper
Computing weighted subset transversals in \(H\)-free graphs2022-03-25Paper
What Graphs are 2-Dot Product Graphs?2022-02-01Paper
Computing subset transversals in \(H\)-free graphs2022-01-18Paper
https://portal.mardi4nfdi.de/entity/Q50051662021-08-04Paper
Steiner trees for hereditary graph classes: a treewidth perspective2021-04-15Paper
Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy2021-04-08Paper
Clique-width for hereditary graph classes2021-02-06Paper
Independent Feedback Vertex Set for P_5-free Graphs2020-11-25Paper
On cycle transversals and their connected variants in the absence of a small linear forest2020-10-12Paper
Computing Weighted Subset Transversals in $H$-Free Graphs2020-07-28Paper
Filling the complexity gaps for colouring planar and bounded degree graphs2020-07-17Paper
Clique-Width for Graph Classes Closed under Complementation2020-06-09Paper
Computing Subset Transversals in $H$-Free Graphs2020-05-28Paper
Recognizing Graphs Close to Bipartite Graphs2020-05-26Paper
https://portal.mardi4nfdi.de/entity/Q51112902020-05-26Paper
On cycle transversals and their connected variants in the absence of a small linear forest2020-01-30Paper
Graph isomorphism for \((H_1,H_2)\)-free graphs: an almost complete dichotomy2020-01-16Paper
Connected vertex cover for \((sP_1+P_5)\)-free graphs2020-01-16Paper
Surjective H-colouring: New hardness results2019-10-28Paper
On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal2019-10-11Paper
Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide2019-08-15Paper
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest2019-08-01Paper
Independent feedback vertex set for \(P_5\)-free graphs2019-04-25Paper
On a conjecture of Mohar concerning Kempe equivalence of regular graphs2019-02-08Paper
Graph Isomorphism for $(H_1,H_2)$-free Graphs: An Almost Complete Dichotomy2018-11-29Paper
Connected vertex cover for \((sP_1+P_5)\)-free graphs2018-11-22Paper
Enclosings of decompositions of complete multigraphs in 2‐factorizations2018-10-05Paper
Independent feedback vertex sets for graphs of bounded diameter2017-12-13Paper
Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity2017-11-16Paper
Obtaining online ecological colourings by generalizing first-fit2017-11-07Paper
Surjective \(H\)-colouring: new hardness results2017-08-04Paper
A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs2017-04-21Paper
A Reconfigurations Analogue of Brooks' Theorem and Its Consequences2016-11-17Paper
What graphs are 2-dot product graphs?2016-10-14Paper
Kempe equivalence of colourings of cubic graphs2016-10-14Paper
Kempe equivalence of colourings of cubic graphs2016-10-12Paper
Finding shortest paths between graph colourings2016-09-07Paper
The price of connectivity for cycle transversals2016-08-16Paper
Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs2016-04-04Paper
The Price of Connectivity for Cycle Transversals2015-09-16Paper
Finding Shortest Paths Between Graph Colourings2015-09-15Paper
Knocking out \(P_k\)-free graphs2015-07-06Paper
Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs2015-05-20Paper
A Reconfigurations Analogue of Brooks’ Theorem2014-10-14Paper
Knocking Out P k -free Graphs2014-10-14Paper
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs2014-02-25Paper
Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs2014-01-14Paper
https://portal.mardi4nfdi.de/entity/Q28573382013-11-01Paper
https://portal.mardi4nfdi.de/entity/Q31042552011-12-19Paper
https://portal.mardi4nfdi.de/entity/Q31042712011-12-19Paper
Finding paths between 3-colorings2011-05-11Paper
Obtaining Online Ecological Colourings by Generalizing First-Fit2010-06-22Paper
Path factors and parallel knock-out schemes of almost claw-free graphs2010-05-05Paper
Mixing 3-colourings in bipartite graphs2009-11-30Paper
Upper bounds and algorithms for parallel knock-out numbers2009-03-30Paper
The Computational Complexity of the Parallel Knock-Out Problem2008-09-18Paper
Mixing 3-Colourings in Bipartite Graphs2008-07-01Paper
Finding Paths between Graph Colourings: Computational Complexity and Possible Distances2008-06-05Paper
The computational complexity of the parallel knock-out problem2008-04-15Paper
Transversals of subtree hypergraphs and the source location problem in digraphs2008-03-12Paper
Connectedness of the graph of vertex-colourings2008-02-14Paper
Upper Bounds and Algorithms for Parallel Knock-Out Numbers2007-11-15Paper
https://portal.mardi4nfdi.de/entity/Q53102302007-09-21Paper
Amalgamations of factorizations of complete graphs2007-06-08Paper
Amalgamations of factorizations of complete equipartite graphs2004-08-20Paper
Characterization of graphs with hall number 22004-03-15Paper
Amalgamations of connected \(k\)-factorizations.2003-08-17Paper
An algorithm for finding factorizations of complete graphs2003-06-25Paper
Defining sets for Latin squares given that they are based on groups2003-04-09Paper
SOME RESULTS ON THE OBERWOLFACH PROBLEM2002-10-22Paper
https://portal.mardi4nfdi.de/entity/Q27125302001-07-17Paper
Weak Uniquely Completable Sets for Finite Groups2000-06-22Paper

Research outcomes over time


Doctoral students

No records found.


Known relations from the MaRDI Knowledge Graph

PropertyValue
MaRDI profile typeMaRDI person profile
instance ofhuman


This page was built for person: Matthew Johnson