Matthew Johnson

activity

20142025

most citedA Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs

25 citations · 79 across the 15 of their papers we have counts for

collaborators

Showing 2016Show all

3 papers · 1 filter

math.CO2016

Enclosings of Decompositions of Complete Multigraphs in 2-Factorizations

Carl Feghali, Matthew Johnson

Let $k$ , $λ$ and $μ$ be positive integers. A decomposition of a multigraph $λ G$ into edge-disjoint subgraphs $G_{1}, \dots, G_{k}$ is said to be \emph{enclosed} by a decomposition o…

cs.DS2016★ 3 cited

Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide

Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson +1

A graph is $(H_{1}, H_{2})$ -free for a pair of graphs $H_{1}, H_{2}$ if it contains no induced subgraph isomorphic to $H_{1}$ or $H_{2}$ . In 2001, Král', Kratochv\'ıl, Tuza, and Woeginger initia…

cs.DS2016★ 1 cited

A Serial Multilevel Hypergraph Partitioning Algorithm

Foad Lotfifar, Matthew Johnson

The graph partitioning problem has many applications in scientific computing such as computer aided design, data mining, image compression and other applications with sparse-matrix…