Magdalena Prorok

activity

20242026

collaborators

8 papers

math.CO2026

Cycle lengths in graphs of given minimum degree

Yandong Bai, Andrzej Grzesik, Binlong Li +1

We prove that if $G$ is a 2-connected graph with minimum degree at least $k ⩾ 4$ , then (1) $G$ contains $k$ cycles whose lengths form an arithmetic progression with common d…

math.CO2026

Strong Majority Edge-Coloring

Sylwia Antoniuk, Magdalena Prorok, Nika Salia

A strong majority edge-coloring of a graph is an edge-coloring in which, for every edge $e$ and every color $i$ , at most half of the edges adjacent to $e$ have color $i$ . Such a co…

math.CO2026

On 3-colorability of (claw, diamond)-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 $(c l a w, d iam o n d, K_{4})$ -free graphs. Recently, $3$ -colorability has been also conside…

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

Cycle lengths in graphs of given minimum degree

Strong Majority Edge-Coloring

On 3-colorability of (claw, diamond)-free graphs

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