Marta Piecyk

activity

20242026

collaborators

6 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

On the complexity of edge subdivision to $H$ -free graphs

Marta Piecyk, R. B. Sandeep

Subdividing an edge $uv$ in a graph replaces it by a path $u w v$ with one new vertex. For a graph $H$ , the \textsc{ $H$ -free Subdivision} problem asks whether, given a graph $G$ an…

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 $Ï…