Magdalena Prorok

activity

20232026

most citedThe dimension of the region of feasible tournament profiles

1 citations · 1 across the 7 of their papers we have counts for

collaborators

9 papers

math.CO2026

Proof of the mad conjecture and its coloring applications

Andrzej Grzesik, Lenka Kopfová, Gaurav Kucheriya +2

For a finite graph $G$ , the maximum average degree $mad (G)$ is the largest average degree of a nonempty subgraph of $G$ . Hendrey, Norin and Wood asked whether this p…

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

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

math.CO2024

On 3-colourability of $(b u l l, H)$ -free graphs

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

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

math.CO2023★ 1 cited

The dimension of the region of feasible tournament profiles

Daniel Kral, Ander Lamaison, Magdalena Prorok +1

Erd\H os, Lovász and Spencer showed in the late 1970s that the dimension of the region of $k$ -vertex graph profiles, i.e., the region of feasible densities of $k$ -vertex graphs in…

Proof of the mad conjecture and its coloring applications

Strong Majority Edge-Coloring

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

Cycle lengths in graphs of given minimum degree

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 3-colourability of (bull,H)-free graphs

The dimension of the region of feasible tournament profiles

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

On 3-colourability of $(b u l l, H)$ -free graphs