Marta Piecyk

activity

20202022

collaborators

4 papers

math.CO2022

Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws

Michał Dębski, Zbigniew Lonc, Karolina Okrasa +2

For graphs $G$ and $H$ , an $H$ -coloring of $G$ is an edge-preserving mapping from $V (G)$ to $V (H)$ . In the $H$ -Coloring problem the graph $H$ is fixed and we ask whether an instanc…

cs.DS2021

Faster 3-coloring of small-diameter graphs

Michał Dębski, Marta Piecyk, Paweł Rzążewski

We study the 3-\textsc{Coloring} problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for $n$ -vertex diameter-2 graphs this problem can be solved in su…

cs.CC2020

Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth

Marta Piecyk, Paweł Rzążewski

For graphs $G, H$ , a homomorphism from $G$ to $H$ is an edge-preserving mapping from $V (G)$ to $V (H)$ . In the list homomorphism problem, denoted by \textsc{LHom}( $H$ ), we are given…

cs.CC2020

Full complexity classification of the list homomorphism problem for bounded-treewidth graphs

Karolina Okrasa, Marta Piecyk, Paweł Rzążewski

A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V (G)$ to $V (H)$ . Let $H$ be a fixed graph with possible loops. In the list homomorphism problem,…