Magdalena Prorok

collaborators

3 papers

math.CO2025

On $k$ -colorability of $(b u l l, H)$ -free graphs

Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1

The $3$ -colorability problem is a well-known NP-complete problem and it remains NP-complete for $b u l l$ -free graphs, where a $b u l l$ is the graph consisting of a $K_{3}$ with two penda…

math.CO2025

Distinguishing symmetric digraphs by proper arc-colourings of type I

Rafał Kalinowski, Monika Pilśniak, Magdalena Prorok

A symmetric digraph $G$ is obtained from a simple graph $G$ by replacing each edge $uv$ with a pair of opposite arcs $uv$ , $v u$ . An arc-…

cs.CC2025

Finding large $k$ -colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs

Nadzieja Hodur, Monika Pilśniak, Magdalena Prorok +1

We study the Max Partial $k$ -Coloring problem, where we are given a vertex-weighted graph, and we ask for a maximum-weight induced subgraph that admits a proper $k$ -coloring. For $…

On k-colorability of (bull,H)-free graphs

Distinguishing symmetric digraphs by proper arc-colourings of type I

Finding large k-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs

On $k$ -colorability of $(b u l l, H)$ -free graphs

Finding large $k$ -colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs