Marta Piecyk

activity

20202026

collaborators

11 papers

cs.DS2026

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs

Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski

The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, ther…

cs.DS2026

A Complexity Dichotomy for Edge Subdivision to $H$ -Free Graphs

Marta Piecyk, R. B. Sandeep

For a fixed graph $H$ , \HFS\ asks whether at most $k$ edge subdivisions can make an input graph contain no induced copy of $H$ . We establish a complexity dichotomy for every fixed…

math.CO2025

List coloring ordered graphs with forbidden induced subgraphs

Marta Piecyk, Paweł Rzążewski

In the List $k$ -Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of ${1, \dots, k}$ . We need to decide if $G$ admits a proper co…

cs.DM2025

On Approximate MMS Allocations on Restricted Graph Classes

Václav Blažej, Michał Dębski, Zbigniew Lonc +2

We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected…

math.CO2025

Kernelization for list $H$ -coloring for graphs with small vertex cover

Marta Piecyk, Astrid Pieterse, Paweł Rzążewski +1

For a fixed graph $H$ , in the List $H$ -Coloring problem, we are given a graph $G$ along with list $L (v) \subseteq V (H)$ for every $v \in V (G)$ , and we have to determine if there ex…

math.CO2024

$C_{2 k + 1}$ -coloring of bounded-diameter graphs

Marta Piecyk

For a fixed graph $H$ , in the graph homomorphism problem, denoted by $H o m (H)$ , we are given a graph $G$ and we have to determine whether there exists an edge-preserving mapping $φ:…

cs.DM2023

Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters

Carla Groenland, Isja Mannens, Jesper Nederlof +2

A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V (G)$ to $V (H)$ . In the graph homomorphism problem, denoted by $H o m (H)$ , the graph $H$ is fixed a…

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,…