Konrad K. Dabrowski

activity

20132026

most citedClique-Width for Hereditary Graph Classes

25 citations · 34 across the 16 of their papers we have counts for

collaborators

Showing 2019Show all

3 papers · 1 filter

math.CO2019★ 1 cited

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

Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani +2

Let $v c (G)$ , $f v s (G)$ and $oc t (G)$ , respectively, denote the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph $G$ . One can a…

cs.DS2019

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest

Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3

A graph is $H$ -free if it contains no induced subgraph isomorphic to $H$ . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…

math.CO2019★ 25 cited

Clique-Width for Hereditary Graph Classes

Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class $G$ is bounded by a constant,…