Matthew Johnson

activity

20172020

most citedOn the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

1 citations · 1 across the 3 of their papers we have counts for

collaborators

Showing cs.DMShow all

2 papers · 1 filter

cs.DM2018

Graph Isomorphism for $(H_{1}, H_{2})$ -free Graphs: An Almost Complete Dichotomy

Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski +3

We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $H_{1}$ and $H_{2}$ for all but six pairs $(H_1,H_2)…

cs.DM2017

Clique-Width for Graph Classes Closed under Complementation

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

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite)…

Graph Isomorphism for (H1​,H2​)-free Graphs: An Almost Complete Dichotomy

Clique-Width for Graph Classes Closed under Complementation

Graph Isomorphism for $(H_{1}, H_{2})$ -free Graphs: An Almost Complete Dichotomy