Konrad K. Dabrowski

activity

20172022

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

3 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

Contracting Bipartite Graphs to Paths and Cycles

Konrad K. Dabrowski, Daniël Paulusma

Testing if a given graph $G$ contains the $k$ -vertex path $P_{k}$ as a minor or as an induced minor is trivial for every fixed integer $k \geq 1$ . However, the situation changes for t…

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

Contracting Bipartite Graphs to Paths and Cycles

Clique-Width for Graph Classes Closed under Complementation

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