Paweł Rzążewski

activity

20182020

most citedFinding large induced sparse subgraphs in

C_{> t}

-free graphs in quasipolynomial time

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

collaborators

3 papers

cs.DS2020★ 6 cited

Finding large induced sparse subgraphs in $C_{> t}$ -free graphs in quasipolynomial time

Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk +2

For an integer $t$ , a graph $G$ is called {\em{ $C_{> t}$ -free}} if $G$ does not contain any induced cycle on more than~ $t$ vertices. We prove the following statement: for every pair…

cs.CC2019

Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs

Karolina Okrasa, Paweł Rzążewski

For graphs $G$ and $H$ , a \emph{homomorphism} from $G$ to $H$ is an edge-preserving mapping from the vertex set of $G$ to the vertex set of $H$ . For a fixed graph $H$ , by \textsc{H…

cs.DM2018★ 2 cited

$H$ -colouring $P_{t}$ -free graphs in subexponential time

Carla Groenland, Karolina Okrasa, Pawel Rzążewski +3

A graph is called $P_{t}$ -free if it does not contain the path on $t$ vertices as an induced subgraph. Let $H$ be a multigraph with the property that any two distinct vertices share…

Finding large induced sparse subgraphs in C>t​-free graphs in quasipolynomial time

Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs

H-colouring Pt​-free graphs in subexponential time

Finding large induced sparse subgraphs in $C_{> t}$ -free graphs in quasipolynomial time

$H$ -colouring $P_{t}$ -free graphs in subexponential time